Opening Razborov Smolensky Lower Bounds for AC0[p]
Razborov Smolensky Lower Bounds for AC0[p]
- Length
- 1 h 13 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 7: Circuit lower bounds and mod p gates
Builds low-degree polynomials for AC0[3] circuits gate by gate, then proves parity admits none.
The Razborov–Smolensky method proves that constant-depth circuits with mod 3 gates need exponential size to compute parity. O'Donnell, in session 22 of CMU's graduate complexity course 15-855, shows that any AC0[3] circuit is approximated by a low-degree polynomial over . Fermat's Little Theorem lets each AND, OR and mod gate be replaced in turn by a randomized polynomial. O'Donnell checks properness, degree and error, then cuts the randomness to polylog bits with Valiant-Vazirani style hashing. A binomial-coefficient counting argument over multilinear polynomials on the boolean cube shows that approximating parity requires degree at least .
The Razborov–Smolensky method proves that constant-depth circuits with mod 3 gates need exponential size to compute parity. O'Donnell, in session 22 of CMU's graduate complexity course 15-855, shows that any AC0[3] circuit is approximated by a low-degree polynomial over . Fermat's Little Theorem lets each AND, OR and mod gate be replaced in turn by a randomized polynomial. O'Donnell checks properness, degree and error, then cuts the randomness to polylog bits with Valiant-Vazirani style hashing. A binomial-coefficient counting argument over multilinear polynomials on the boolean cube shows that approximating parity requires degree at least .
Håstad'86
Raz'87
Smol'87

This lecture
Lecture 22 of 27 of Graduate Computational Complexity Theory.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in