Non-uniform ACC Circuit Lower Bounds

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. We prove: 1. NTIME[2ⁿ] does not have non-uniform ACC circuits of polynomial size. The size lower bound can be strengthened to quasi-polynomials and other less natural functions. 2. E^NP, the class of languages recognized in 2^O(n) time with an NP oracle, doesn´t have non-uniform ACC circuits of 2^no(1) size. The lower bound gives a size-depth tradeoff: for every d, m there is a δ >; 0 such that E^NP doesn´t have s depth-d ACC circuits of size 2^nδ with MOD_m gates. Previously, it was not known whether EXP^NP had depth-3 polynomial size circuits made out of only MOD₆ gates. 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 obtain the above lower bounds.