Circuits of Bounded Depth
summary
Claims an exponential lower bound: any depth-d arithmetic circuit computing the n×n determinant needs size at least exp(Ω(n^{1/d})), proven by exhibiting explicit polynomials with 2^n monomials and tracking monomial support under bounded-depth composition. The proof uses the partial-derivative / shifted partials method and a representation lemma that limits how many monomials a small bounded-depth subcircuit can produce. The construction is explicit and the bound matches depth-reduction tradeoffs up to polynomial factors.
AI-written summary · about
chapters (7)
- 0:00Bounded depth circuits intro
- 1:09Arithmetic circuits and polynomials
- 17:57Complexity and circuit classes
- 28:23Determinants and quasipolynomial bounds
- 48:57Applications in games and learning
- 1:03:48Open problems and future work
- 1:24:43Summary
related talks
23mWorst-Case to Expander-Case Reductions
33mLower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems
25mBit Complexity of Jordan Normal Form and Spectral Factorization
25mExponential separations using guarded extension variables
01h 02mFine-Grained Counting Complexity I
31mNew Unconditional Lower Bounds for Algorithms and Enumeration Problems
38mLower Bounds on the Space Complexity of Dynamic Programming
20mSymmetric Formulas for Products of Permutations