5
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ I think this is on-topic for cstheory (not saying that it is not on-topic here). $\endgroup$
    – Kaveh
    Feb 14, 2013 at 21:52

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Sam Buss
    Feb 18, 2013 at 3:01
  • $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    Feb 19, 2013 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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