# 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

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