Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 4 down vote favorite

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$?

share|improve this question
1  
I think this is on-topic for cstheory (not saying that it is not on-topic here). – Kaveh Feb 14 at 21:52

1 Answer

up vote 7 down vote accepted

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.)

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.