A Review of Some Recent Lower Bounds Against Low-Depth Threshold Circuits

on YouTube ↗33m

" summary

Presents concrete lower bounds: an explicit Andreev-style function needs superlinear gates and roughly n^{1.5}/polylog n size against depth‑3 TC0, proven by a random‑restriction lemma that makes an LTF constant with probability 1 − O(K/√n) when only K inputs remain, and a counting lower bound on the restricted function. Develops probabilistic polynomials and probabilistic PTFs (degree ~√(D log S) or improved cube‑root tradeoffs), yields faster SAT for ACC-of-thresholds with a sub‑quadratic bottom layer and an E^NP circuit lower bound.

AI-written summary · about

" chapters (13)

1. 0:00Start
2. 0:50Outline
3. 2:34Introduction
4. 3:32Depth-Two LTF Circuits
5. 6:21Lower Bounds for Explicit Functions
6. 7:59Thm 1: Andreev's Function A'87
7. 10:01Thm 1: Andreev's Function [A'87]
8. 11:28THR-THR Lower Bound for Andreev?
9. 14:21Random Restrictions to LTFs
10. 15:57Let's take a moment to adjust our eyes...
11. 16:17Probabilistic Polynomials for Functions
12. 21:41Applications for Circuit Complexity
13. 29:09Open Problems Tight upper and lower bounds for Andreev?