Parity and $AC^0$ are like inseparable twins. Or so it has seemed for the last 30 years. In the light of Ryan's result, there will be renewed interest in the small classes.

Furst Saxe Sipser to Yao to Hastad are all parity and random restrictions. Razborov/Smolensky is approximate polynomial with parity (ok, mod gates). Aspnes et al use weak degree on parity. Further, Allender Hertrampf and Beigel Tarui are about using Toda for small classes. And Razborov/Beame with decision trees. All of these fall into the parity basket.

1) What are other natural problems (apart from parity) that can be shown directly not to be in $AC^0$?

2) Anyone know of a drastically different approach to lower bound on AC^0 that has been tried?


Benjamin Rossman's result on $AC^0$ lowerbound for k-clique from STOC 2008.


  • $\begingroup$ Is not Rossman subsumed by Beame's primer which also had clique in it? The arguments are more intricate, of course. $\endgroup$ – V Vinay Nov 19 '10 at 1:13
  • $\begingroup$ @V Vinay: can you give a link to Paul Beame's article? $\endgroup$ – Kaveh Nov 19 '10 at 1:21
  • 4
    $\begingroup$ Rossman's result shows that $k$-clique cannot be computed by constant-depth circuits of size $\Omega(n^{k/4})$. Note that the constant in the exponent does not depend on the depth of the circuit, which is where it improves on Beame's $n^{\Omega(k/d^2)}$ lower bound. $\endgroup$ – Srikanth Nov 19 '10 at 2:49
  • $\begingroup$ @Srikanth, I thought that V Vinay is saying Beame has a newer result but I was not able to find any on his page. Thanks for clarification. $\endgroup$ – Kaveh Nov 19 '10 at 3:49
  • 1
    $\begingroup$ Srikanth is right about the bounds. Kaveh, not a new paper; I used "subsumed" in the sense that I had listed Beame in my question and was hence aware of the clique lower bound. $\endgroup$ – V Vinay Nov 19 '10 at 8:26

There is the "top-down" approach by Håstad, Jukna and Pudlák, as done in their paper Top-down lower bounds for depth-three circuits. Unfortunately we have so far not been able to extend the approach to higher depths.

  • $\begingroup$ Yes. I thought you had a paper influenced by this approach? $\endgroup$ – V Vinay Nov 19 '10 at 1:01

1) The first that comes to my mind is MAJORITY. You can prove that it is not in $AC^{0}$ with the same techniques. See Håstad's thesis for details.

2) A topological approach, again working only for depth-three circuits, was proposed by Kriegel and Waack.

  • 2
    $\begingroup$ Majority is the same thing really. I should have mentioned it though. Also, there was a paper by Boppana on Majority in the mid-80's. $\endgroup$ – V Vinay Nov 19 '10 at 1:10

The other two "classical" methods are Haken's bottleneck method and Karchmer's fusion method (so named by Avi Wigderson), both much easier to apply in the monotone setting.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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