Research map / Learning theory and algorithms / Sample complexity
On a Combinatorial Problem Arising in Machine Teaching
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves a conjecture of Ferri et al. (2024) that, for the size-based Greedy machine-teaching model, the minimum of the sum of distinct-row counts over q-column projections is achieved by the binary-counting matrix H_{n,k}, generalizing the hypercube edge-isoperimetry result.
Problem
Machine teaching with a size-based teacher mapping: determining the worst-case teaching dimension of the Greedy algorithm as a function of concept class size, which reduces to a combinatorial minimization over binary matrices with k distinct rows and n columns.
Approach
Shows that the minimum over k-row, n-column binary matrices (distinct rows) of the total number of distinct rows over all q-column projections is attained by the matrix of binary representations of 0..k-1, by a recursive splitting argument and a Hamming-weight bijection lemma that generalizes the hypercube edge-isoperimetric result.
Key results
- Proves that m_q(n,k) = h_q(n,k) for all 1 <= q <= n and k <= 2^n, i.e., the binary-counting matrix H_{n,k} minimizes the sum of distinct rows over q-column projections.
- Specializing to q = n-1 recovers the hypercube edge-isoperimetric theorem (maximum edges in induced k-vertex subgraphs).
Limitations
- Only the extremal value is characterized; the complexity of computing m_q(M) for a general matrix is left open.
- The result concerns the worst case of the Greedy model, not optimal teaching dimension in other models.
Experimental setup
Builds on: Greedy teacher construction (Ferri et al., 2024) edge isoperimetry of the hypercube
Closest papers by meaning
- Machine Learning meets Algebraic Combinatorics: A Suite of Datasets Capturing Research-level Conjecturing Ability in Pure Mathematics (ICML 2025 · similarity 0.87)
- The Computational Complexity of Positive Non-Clashing Teaching in Graphs (ICLR 2025 · similarity 0.86)
- Replicability in Learning: Geometric Partitions and KKM-Sperner Lemma (NeurIPS 2024 · similarity 0.84)
- A Trichotomy for List Transductive Online Learning (ICML 2025 · similarity 0.82)
- Neural Discovery in Mathematics: Do Machines Dream of Colored Planes? (ICML 2025 · similarity 0.82)
- ONLINE EPSILON NET & PIERCING SET FOR GEOMETRIC CONCEPTS (ICLR 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.