Opening Monotone Circuit Lower Bounds
Monotone Circuit Lower Bounds
- Length
- 1 h 24 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 10: Monotone functions and monotone circuits
Proves an exponential lower bound for monotone circuits computing Andreyev's explicit function in NP.
Monotone circuit lower bounds measure how large a circuit of AND and OR gates, with no negations, must be to compute a monotone Boolean function. O'Donnell, in session 21 of Carnegie Mellon's graduate complexity course CMU 15-855, defines monotone functions and circuits and reviews Razborov's super-polynomial bound for clique. He then states and proves the monotone switching lemma, using witness trees to sandwich a small CNF between a narrow DNF and a bounded error set. A structural induction over gates turns the lemma into an approximation theorem in which errors grow in proportion to circuit size. The final part defines Andreyev's function from polynomials over finite fields, then completes the exponential bound with a degree argument and a random-input probability bound.
Monotone circuit lower bounds measure how large a circuit of AND and OR gates, with no negations, must be to compute a monotone Boolean function. O'Donnell, in session 21 of Carnegie Mellon's graduate complexity course CMU 15-855, defines monotone functions and circuits and reviews Razborov's super-polynomial bound for clique. He then states and proves the monotone switching lemma, using witness trees to sandwich a small CNF between a narrow DNF and a bounded error set. A structural induction over gates turns the lemma into an approximation theorem in which errors grow in proportion to circuit size. The final part defines Andreyev's function from polynomials over finite fields, then completes the exponential bound with a degree argument and a random-input probability bound.
Alon and Boppana 1987
Andreyev 1985, 1987
Harnick and Raz 2000
This lecture
Lecture 21 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
Tardos 1987
Norbert Blum 2017
Gyarfas, Stash, Jukna, and Bergen Ulfberg 1986