Recent Structure Lemmas for Depth-two Threshold Circuits

on YouTube ↗28m

" summary

Shows two explicit structure lemmas: any poly-size depth-2 threshold circuit is constructively written as a disjoint OR decomposition into majority-of-majority subcircuits with a tradeoff: top fan-in 2^{εn} and each subcircuit size S^{1/ε}, or the reverse (polynomial top fan-in and sub-exponential subcircuits). Proves algorithmic equivalences (SAT and approximate acceptance) between threshold and majority classes, reduces hardness to geometry problems like bipartite closest pair reduction and point–hyperplane incidence, and deduces that any nontrivial SAT/CAP saving yields NEXP ⊄ poly-size depth-2 threshold; asks about OR of two majority-of-majority lower bounds.

AI-written summary · about

" chapters (20)

1. 0:00Introduction to circuits
2. 1:44Algorithmic lower bounds
3. 2:38Defining satisfiability
4. 3:36Equivalence and results
5. 5:07Structural lemma
6. 6:33Circuit optimization
7. 7:27Simplifying circuits
8. 8:55Circuit transformation
9. 10:42Open questions
10. 11:37Depth increase issues
11. 12:20Threshold circuits
12. 13:15Circuit reduction
13. 14:35Evaluation vs satisfaction
14. 15:53Complexity lower bounds
15. 16:40Geometric reduction
16. 18:19Approximate evaluation
17. 19:32Circuit depth analysis
18. 20:53Running time improvement
19. 21:24Summary of results
20. 22:34Q&A and conclusion