# Simple lower bounds against AC0

It is known that $Parity \notin AC^0$ (nonuniform), but the proof is rather involved and combinatorial. Are there simpler, but weaker lower bounds, say for $NP \not \subseteq AC^0$ or $NEXP \not \subseteq AC^0$?

For example, can nontrivial simplifications be obtained in the proof of $NEXP \not \subseteq ACC^0$ to deal only with the special case of $AC^0$?

• I think this is on-topic for cstheory (not saying that it is not on-topic here). – Kaveh Feb 14 '13 at 21:52

## 1 Answer

I guess it depends on your point of view, but the proof via approximating polynomials (along the lines of Razborov-Smolensky) that Parity isn't in AC0 is not so involved...

The natural way in which one would modify the proof that "NEXP is not in ACC0" to yield "NEXP not in AC0" would be to give a SAT algorithm for AC0 circuits that beats exhaustive search. However, all known SAT algorithms of this kind actually use the same or similar techniques as the "Parity not in AC0" lower bounds, so the proof would not get any simpler. (It would be interesting to find an AC0 SAT algorithm where this is not the case.)

• What are the best sources for these algorithms for satisfiability of $AC^0$ circuits? In historical order, there are "The Complexity of Satisfiability of Small Depth Circuits" by C. Calabro, R. Impagliazzo and R. Paturi; and also "A Satisfiability Algorithm for $AC^0$", by R. Impagliazzo, W. Matthews and R. Paturi. Are there any other known algorithms? – Sam Buss Feb 18 '13 at 3:01
• Hi Sam, admittedly there are few such algorithms. The others I know are that which follows from the ACC sat algorithm (earlier work based on Razborov and Smolensky show that AC0 can be represented as a SYM of ANDs with better parameters than what you get for ACC, which you can then plug into the ACC SAT algorithm) and Paul Beame, Russell Impagliazzo, and Srikanth Srinivasan. Approximating AC0 circuits by small height decision trees and a deterministic algorithm for AC0-SAT. – Ryan Williams Feb 19 '13 at 2:48