Opening Ironic Complexity
Ironic Complexity
- Length
- 1 h 20 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 12: Before the lecture
Proves Williams's theorem: a non-trivial SAT algorithm for a circuit class keeps out of that class.
Williams's theorem links faster-than-brute-force satisfiability algorithms for a circuit class to lower bounds placing outside that class. O'Donnell opens with circuit lower bounds from the 1980s and early 1990s, including Håstad's bounds for parity, then gives two warmup proofs from deterministic and subexponential-time SAT algorithms. The main proof is an indirect diagonalization that assumes the contrary and picks a hard language from the nondeterministic time hierarchy theorem. Its ingredients are succinct 3SAT, the easy witness method, lexicographically least assignments found in , and a quasilinear, constant-depth form of the reduction of Cook and Levin. Guessing a witness circuit and checking its clauses with the assumed SAT solver yields the contradiction. Session 28 of CMU 15-855 assumes Karp-Lipton theorems, , and basic derandomization.
Williams's theorem links faster-than-brute-force satisfiability algorithms for a circuit class to lower bounds placing outside that class. O'Donnell opens with circuit lower bounds from the 1980s and early 1990s, including Håstad's bounds for parity, then gives two warmup proofs from deterministic and subexponential-time SAT algorithms. The main proof is an indirect diagonalization that assumes the contrary and picks a hard language from the nondeterministic time hierarchy theorem. Its ingredients are succinct 3SAT, the easy witness method, lexicographically least assignments found in , and a quasilinear, constant-depth form of the reduction of Cook and Levin. Guessing a witness circuit and checking its clauses with the assumed SAT solver yields the contradiction. Session 28 of CMU 15-855 assumes Karp-Lipton theorems, , and basic derandomization.
Ironic Complexity
PPZ 97
Lemma 20.20 (Test 2)
Papers from 2010 and 2011

This lecture
Lecture 27 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. 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
Jachau, Milos, and Viola (2014)
Bonus [Jahanjoo-Miles-Viohl 2017]