<p><a href="http://www.mit.edu/~brossman/">Benjamin Rossman</a>'s result on $AC^0$ lowerbound for k-clique from STOC 2008.</p>

<hr>

<p>References:</p>

<ul>
<li>Paul Beame, "<a href="http://www.cs.washington.edu/homes/beame/papers/primer.ps">A Switching Lemma Primer</a>", Technical Report 1994.</li>
<li>Benjamin Rossman, "<a href="http://www.mit.edu/~brossman/k-clique-stoc.pdf">On the Constant-Depth Complexity of k-Clique</a>", STOC 2008.</li>
</ul>

CC BY-SA 2.5
2010-11-19T01:13:26.693Z
Is not Rossman subsumed by Beame's primer which also had clique in it? The arguments are more intricate, of course.
V Vinay
CC BY-SA 2.5
2010-11-19T01:21:57.730Z
@V Vinay: can you give a link to Paul Beame's article?
Kaveh
CC BY-SA 2.5
2010-11-19T02:49:15.330Z
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.
Srikanth
CC BY-SA 2.5
2010-11-19T03:49:06.143Z
@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.
Kaveh
CC BY-SA 2.5
2010-11-19T08:26:05.293Z
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.
V Vinay
CC BY-SA 2.5
2010-11-18T19:36:09.507Z
2010-11-20T10:50:04.913Z
2010-11-20T10:50:04.913Z
Kaveh
<p>There is the "top-down" approach by Håstad, Jukna and Pudlák, as done in their paper <a href="http://dx.doi.org/10.1007/BF01268140" rel="noreferrer">Top-down lower bounds for depth-three circuits</a>. Unfortunately we have so far not been able to extend the approach to higher depths.</p>

CC BY-SA 2.5
2010-11-19T01:01:06.860Z
Yes. I thought you had a paper influenced by this approach?
V Vinay
CC BY-SA 2.5
2010-11-18T19:49:17.927Z
2010-11-18T19:49:17.927Z
Kristoffer Arnsfelt Hansen
<p>The other two "classical" methods are Haken's bottleneck method and Karchmer's <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AVI/HUNGARY/proc.pdf" rel="noreferrer">fusion method</a> (so named by Avi Wigderson), both much easier to apply in the monotone setting.</p>

CC BY-SA 2.5
2010-11-20T23:20:09.237Z
2010-11-20T23:20:09.237Z
Yuval Filmus
<ol>
<li><p>The first that comes to my mind is MAJORITY. You can prove that it is not in <span class="math-container">$AC^{0}$</span> with the same techniques. See <a href="https://www.csc.kth.se/%7Ejohanh/thesis_with_figs.pdf" rel="nofollow noreferrer" title="J. Håstad, Computational limitations for small depth circuits, a book manuscript based on Ph.D-thesis, 1986">Håstad's thesis</a> for details.</p>
</li>
<li><p>A topological approach, again working only for depth-three circuits, was proposed by <a href="https://doi.org/10.1007/BFb0028806" rel="nofollow noreferrer" title="Kriegel, K., Waack, S. (1985). Lower bounds for boolean formulae of depth 3 and the topology of the n-Cube (Preliminary version). In: Budach, L. (eds) Fundamentals of Computation Theory. FCT 1985. Lecture Notes in Computer Science, vol 199. Springer, Berlin, Heidelberg">Kriegel and Waack</a>.</p>
</li>
</ol>

CC BY-SA 2.5
2010-11-19T01:10:01.890Z
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.
V Vinay
CC BY-SA 4.0
2010-11-18T19:30:46.173Z
2022-11-24T23:09:16.577Z
2022-11-24T23:09:16.577Z
Alessandro Cosentino
<p>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.</p>

<p>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. </p>

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

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

<cc.complexity-theory><complexity-classes><lower-bounds><circuit-complexity>
Parity and $AC^0$
V Vinay
# Parity and $AC^0$

(Asked by: username_0 on 2010-11-18)

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?

**Tags:** cc.complexity-theory, complexity-classes, lower-bounds, circuit-complexity


---

## 4 answers

### Answer by username_1 on 2010-11-18. Score: 13

[Benjamin Rossman](http://www.mit.edu/~brossman/)'s result on $AC^0$ lowerbound for k-clique from STOC 2008.

---

References:

* Paul Beame, "[A Switching Lemma Primer](http://www.cs.washington.edu/homes/beame/papers/primer.ps)", Technical Report 1994.
* Benjamin Rossman, "[On the Constant-Depth Complexity of k-Clique](http://www.mit.edu/~brossman/k-clique-stoc.pdf)", STOC 2008.

> **Comments:**
> **username_0**: Is not Rossman subsumed by Beame's primer which also had clique in it? The arguments are more intricate, of course.  
> **username_1**: @username_0: can you give a link to Paul Beame's article?  
> **username_2**: 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.  
> **username_1**: @username_2, I thought that username_0 is saying Beame has a newer result but I was not able to find any on his page. Thanks for clarification.  
> **username_0**: username_2 is right about the bounds. username_1, 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.  

---

### Answer by username_3 on 2010-11-18. Score: 12

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](http://dx.doi.org/10.1007/BF01268140). Unfortunately we have so far not been able to extend the approach to higher depths.

> **Comments:**
> **username_0**: Yes. I thought you had a paper influenced by this approach?  

---

### Answer by username_5 on 2010-11-18. Score: 10

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](https://www.csc.kth.se/%7Ejohanh/thesis_with_figs.pdf "J. Håstad, Computational limitations for small depth circuits, a book manuscript based on Ph.D-thesis, 1986") for details.
2. A topological approach, again working only for depth-three circuits, was proposed by [Kriegel and Waack](https://doi.org/10.1007/BFb0028806 "Kriegel, K., Waack, S. (1985). Lower bounds for boolean formulae of depth 3 and the topology of the n-Cube (Preliminary version). In: Budach, L. (eds) Fundamentals of Computation Theory. FCT 1985. Lecture Notes in Computer Science, vol 199. Springer, Berlin, Heidelberg").

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_4 on 2010-11-20. Score: 8

The other two "classical" methods are Haken's bottleneck method and Karchmer's [fusion method](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AVI/HUNGARY/proc.pdf) (so named by Avi Wigderson), both much easier to apply in the monotone setting.


---

