Circuit Complexity and Connections II
summary
Shows concrete equivalences: faster algorithms for restricted circuit SAT give explicit circuit lower bounds, and conversely lower bounds yield derandomization and analysis algorithms. Uses probabilistic polynomials to turn small-depth circuit approximations into faster algorithms — e.g., closest-pair in Hamming space with n red and n blue points in C log n dimensions runs subquadratic (n^{2−1/O(log C)}) time. Defines data complexity (minimum labeled examples to test all size-s circuits) and proves tight equivalences between those data-size bounds and circuit-size upper/lower bounds.
AI-written summary · about
chapters (9)
- 0:00Circuit SAT and lower bounds
- 2:20From lower bounds to algos
- 7:30Mining proofs for algorithms
- 12:12Repeated sub-computation
- 17:10Complexity equivalences
- 27:42Data complexity framework
- 34:31Equivalence theorems
- 44:50Formalizing the duality
- 53:20Synthesis and discussion
related talks
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
01h 21mComputational Complexity in Theory and in Practice
29mImproved Deterministic Algorithms for Sparse Max-SAT
29mAn Isomorphism Between Parameterized Complexity and Classical Complexity, for both Time and Space
10mQuery, Communication and Discrepancy
23mTowards General and Tight Hardness Results for Graph Problems
25mLower Bounds for Problems Parameterized by Clique-width
35mSuperlinear Lower Bounds for Multipass Graph Processing