# 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 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 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 at 2:48