20
$\begingroup$

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?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
13
$\begingroup$

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

References:

Improve this answer
$\endgroup$
5
  • $\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
    Commented Nov 19, 2010 at 1:13
  • $\begingroup$ @V Vinay: can you give a link to Paul Beame's article? $\endgroup$
    – Kaveh
    Commented Nov 19, 2010 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
    Commented Nov 19, 2010 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
    Commented Nov 19, 2010 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
    Commented Nov 19, 2010 at 8:26
12
$\begingroup$

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.

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

  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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Nov 19, 2010 at 1:10
8
$\begingroup$

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.

Improve this answer
$\endgroup$

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.