Opening Toda's Second Theorem and Lower Bounds for Uniform ACC
Toda's Second Theorem and Lower Bounds for Uniform ACC
- Length
- 1 h 16 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 7: Before the lecture
Squashes ACC circuits to symmetric depth-two form via Beigel–Tarui, then separates uniform ACC from PP.
Toda's second theorem places the polynomial-time hierarchy inside with a single sharp-P oracle query, removing the randomness from Toda's first theorem. O'Donnell proves it with modulus amplification polynomials, which lift a count modulo to a count modulo or higher powers. The same polynomials drive the Beigel–Tarui theorem, converting any ACC circuit into a depth-two circuit with a symmetric top gate over polylog-fanin AND gates. With uniformity added, uniform ACC is simulated in sub-exponential time using one sharp-SAT oracle call. Combining that simulation with the time hierarchy theorem yields a contradiction that separates uniform ACC from .
Toda's second theorem places the polynomial-time hierarchy inside with a single sharp-P oracle query, removing the randomness from Toda's first theorem. O'Donnell proves it with modulus amplification polynomials, which lift a count modulo to a count modulo or higher powers. The same polynomials drive the Beigel–Tarui theorem, converting any ACC circuit into a depth-two circuit with a symmetric top gate over polylog-fanin AND gates. With uniformity added, uniform ACC is simulated in sub-exponential time using one sharp-SAT oracle call. Combining that simulation with the time hierarchy theorem yields a contradiction that separates uniform ACC from .
Beigel-Tarui '94
Arora Barak Textbook
Williams's Paper on NEX vs ACC
This lecture
Lecture 23 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
Beigel and Tarui '94