Title: A Satisfiability Algorithm for $\AC^0$ Some small but important corrections
Speaker: Russell Impagliazzo, IAS and UCSD
Date: Wednesday, December 7, 2011 11:00-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We give a new Satisfiability algorithm for constant-depth circuits. More generally, our algorithm describes the set of 1's of the circuit as a disjoint union of restrictions under which the circuit becomes constant. This allows us to count the number of solutions as well as decide Satisfiability. Let $d$ denote the depth of the circuit and $cn$ denote the number of gates. The algorithm runs in expected time $|C| 2^{n(1-\mu_{c.d})}$ where $|C|$ is the size of the circuit and $\mu_{c,d} \ge 1/\bigO[\lg c + d \lg d]^{d-1}$.
As a corollary, we get a tight bound on the maximum correlation of such a circuit with the parity function. (Hastad has also recently shown a similar correlation bound.) The tightness of this bound shows that the time our algorithm takes matches the size of the smallest description as above. By recent results of Ryan Williams, any substantial improvement in our running time, even for Satisfiability, would show that NEXP \not\in NC^1. We use a new generalized switching lemma that applies to families of CNF's, rather than individual CNF's.
Joint work with William Matthews (UCSD, soon to be at Google) and Ramamohan Paturi, (UCSD)