# Parity and $AC^0$

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.

References:

• Is not Rossman subsumed by Beame's primer which also had clique in it? The arguments are more intricate, of course. Nov 19, 2010 at 1:13
• @V Vinay: can you give a link to Paul Beame's article? Nov 19, 2010 at 1:21
• 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. Nov 19, 2010 at 2:49
• @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. Nov 19, 2010 at 3:49
• 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. Nov 19, 2010 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.

• Yes. I thought you had a paper influenced by this approach? Nov 19, 2010 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.

• 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. Nov 19, 2010 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.