Opening Random Restrictions and AC0 Circuit Lower Bounds
Random Restrictions and AC0 Circuit Lower Bounds
- Length
- 1 h 20 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 10: Concrete complexity and constant depth circuits
Proves Håstad's bound that depth- circuits for parity need size 2(Ω(n(1/(d-1)))), via iterated random restrictions.
AC0 circuit lower bounds for parity are built up here, from the depth-two case to Håstad's theorem that depth- circuits need size 2(Ω(n(1/(d-1)))). O'Donnell first shows that any DNF or CNF computing parity must have terms of width . Decision trees then enter, since a tree of height converts into both a CNF and a DNF of width . Random restrictions and the switching lemma collapse wide formulas into shallow trees, and iterating them reduces circuit depth to two. The session in CMU 15-855 assumes basic complexity theory and closes by surveying proofs of the switching lemma.
AC0 circuit lower bounds for parity are built up here, from the depth-two case to Håstad's theorem that depth- circuits need size 2(Ω(n(1/(d-1)))). O'Donnell first shows that any DNF or CNF computing parity must have terms of width . Decision trees then enter, since a tree of height converts into both a CNF and a DNF of width . Random restrictions and the switching lemma collapse wide formulas into shallow trees, and iterating them reduces circuit depth to two. The session in CMU 15-855 assumes basic complexity theory and closes by surveying proofs of the switching lemma.
Håstad's PhD thesis
This lecture
Lecture 19 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