Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique
summary
Reduction from the exponential biclique problem maps a bipartite graph to its adjacency matrix as a concept class, then applies random edge sparsification (keep edges with probability 1/2) to fix completeness. Soundness uses the halving algorithm to prove Littlestone < 2·k2 when no 2^{k2}×k2 biclique exists; completeness yields VC ≥ k1/2 when a 2^{k1}×k1 biclique exists. Consequences: assuming gap‑ETH or SPCH, no polynomial‑time o(log n) approximation and, under SPCH, no n^{o(log n)} time constant‑factor approximation.
AI-written summary · about
chapters (12)
- 0:00Concept Classes
- 1:15VC Dimension
- 2:37Littlestone's Dimension
- 5:09Computational Questions
- 7:11Complexity Assumptions
- 15:34Biclique ⇒ Exponential Biclique
- 16:19Main Reduction
- 19:32Overall Framework: Example
- 22:13Soundness Proof
- 25:09Completeness Proof
- 25:56Final Reduction
- 26:43Conclusion
related talks
47mSuccinct Representations and Efficient Algorithms Based on Linear Programming
41mReducibility and Statistical-Computational Gaps from Secret Leakage
01h 00mOn Approximating the Covering Radius and Finding Dense Lattice Subspaces
35mLocal Statistics, Semidefinite Programming, and Community Detection II
01h 40mBoot camp on generalization theory for graph learning
49mRecent Advances in Counting Sparse Graphs
46mFast Attention Requires Bounded Entries
57mStructure Of Boolean Almost Low Degree Functions On The Biased Cube