A variant of the VC-dimension with applications to depth-3 circuits

on YouTube ↗30m

" summary

Defines a new combinatorial measure, the universal r-dimension, and reduces its extremal estimate to counting independent sets in r-uniform hypergraphs via a squashing argument. For r=2 the extremal family is the Turan graphs, yielding exact Sar–Shelah-style bounds; for higher r the paper gives partial results via iterative edge-removal. Applications translate these bounds into depth-3 circuit limits: every 2-CNF consistent with inner product has at most 3^{n/2} solutions, giving a ~2^{0.2n} lower bound for Σ3,k circuits with small k.

AI-written summary · about

" chapters (12)

1. 0:00Intro
2. 0:21VC-dimension
3. 1:33Sauer-Shelah Lemma
4. 5:31Independent sets in hypergraphs
5. 5:59Independence number
6. 6:52Frankl's squashing
7. 7:45Zykov's theorem
8. 12:54Valiant's program, depth-3 circuits
9. 16:27The toolkit
10. 20:14Bottom fan-in 2, tight result
11. 23:07Bottom fan-in 3, humble progress
12. 25:24Stability approach to depth-3 lower bounds?