Joint Colloquium Distinguished Lecture Series
Non-Uniform ACC Circuit Lower Bounds
 |
Wednesday, February 9, 2011 Ryan Williams Downloadable pdf |
Abstract:
The class ACC consists of circuit families with constant depth over unbounded fan-in AND, OR, NOT, and MODm gates, where m> 1 is an arbitrary constant. Despite the apparent simplicity of such circuit families, the power of MODm has been very hard to reason about: it was not known whether a complexity class as large as EXP^{NP} could be simulated with depth-3 polynomial size circuits made out of only MOD6 gates.
We prove:
- Nondeterministic Exponential Time cannot be simulated with non-uniform ACC circuits of polynomial size. The size lower bound can be slightly strengthened to quasi-polynomials and other less natural
functions.
- E^{NP}, the class of languages recognized in 2^{O(n)} time with an NP oracle, cannot be simulated with non-uniform ACC circuits of 2^{n^{o(1)}} size. The lower bound gives an exponential size-depth tradeoff: for every d and m there is a b> 0 such that E^{NP} doesn't have depth-d ACC circuits of size 2^{n^b} with MODm gates.
The proofs are more interesting than the results. The high-level strategy is to design faster algorithms for the circuit satisfiability problem over ACC circuits, then prove that such algorithms can be applied to yield lower bound proofs against ACC circuits. The algorithms combine known properties of ACC with fast rectangular matrix multiplication and
dynamic programming. The proof connecting algorithms to lower bounds requires a strengthening of the author's prior work [STOC'10].
| Return to EECS Joint Colloquium |