<p>The point is given a general boolean function f there is a monotone boolean function g so that any super linear lower bound on g implies one on f. Or stronger the general complexity of f is equal to the monotone complexity of g up to O(n). </p>

<p>I still am not sure how this relates to the barriers.</p>

CC BY-SA 2.5
2010-12-18T15:19:45.177Z
Welcome to TCS SE!! Many thanks to your blog posts, it is truly a pleasure to read!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-18T15:07:46.147Z
2010-12-18T15:07:46.147Z
dick lipton
<p>Benjamin Rossman's recent paper summarises the state of the art for the monotone circuit complexity of k-CLIQUE.  In short, Razborov proved a lower bound in 1985, later improved by Alon and Boppana in 1987: $\omega(n^k/(\log n)^k)$, versus the brute force upper bound $O(n^k)$.</p>

<p>Rossman shows a lower bound of $\omega(n^{k/4})$ for the average-case complexity in the Erdős-Rényi model of random graphs; Amano previously showed this was essentially also the upper bound.  The quasi-sunflower lemma that forms a key part of the paper is rather neat.</p>

<p>So the natural proofs barrier does not seem to apply to monotone circuit complexity.</p>

<p>Norbert Blum has discussed why lower bounds for monotone circuits are essentially different from circuits with negations.  The key observation of Éva Tardos is that a small modification of the <a href="http://en.wikipedia.org/wiki/Lov%C3%A1sz_number">Lovász theta function</a> has exponential monotone circuit complexity.</p>

<ul>
<li>Benjamin Rossman, <a href="http://www.mit.edu/~brossman/monotone-k-clq.pdf"><em>The Monotone Complexity of k-Clique on Random Graphs</em></a>, FOCS 2010.</li>
<li>Norbert Blum, <a href="http://dx.doi.org/10.1007/978-3-642-03456-5_2"><em>On Negations in Boolean Networks</em></a>, LNCS <strong>5760</strong>, 18–29, 2009.</li>
<li>É. Tardos, <a href="http://www.cs.cornell.edu/People/eva/Gap.Between.Monotone.NonMonotone.Circuit.Complexity.is.Exponential.pdf"><em>The Gap Between Monotone and Non-Monotone Circuit Complexity is Exponential</em></a>, Combinatorica <strong>8</strong>, 141–142, 1987.  <a href="http://dx.doi.org/10.1007/BF02122563">doi:10.1007/BF02122563</a> </li>
</ul>

CC BY-SA 2.5
2010-09-20T21:29:14.647Z
I also found Karchmer's "On proving lower bounds for circuit size" helpful in understanding why monotone circuits are different from circuits with negation.
Kaveh
CC BY-SA 2.5
2010-09-20T14:31:20.970Z
2010-11-11T14:34:16.753Z
2010-11-11T14:34:16.753Z
András Salamon
<p><a href="http://en.wikipedia.org/wiki/Natural_proof">Natural proofs</a> is a barrier towards proving lower bounds on the circuit complexity of boolean functions. They do not directly imply any such barrier in proving lower bounds on the $monotone$ circuit complexity. Is there any progress towards identifying such barriers ? Are there other barriers in the monotone setting ?</p>

CC BY-SA 2.5
2010-09-20T02:38:24.657Z
Didn't Dick Lipton write a post on this a few months ago when discussing natural proofs ? (update): here is the link: http://rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natural-proofs/
Suresh Venkat
CC BY-SA 2.5
2010-09-20T03:18:45.220Z
There are known exponential lower bounds on monotone circuits (Razborov `85, Alon+Boppana `87).
Iddo Tzameret
CC BY-SA 2.5
2010-09-20T05:44:21.840Z
I am interested in more recent developments.
Shiva Kintali
CC BY-SA 2.5
2010-09-20T11:37:21.693Z
Didn't Raz and McKenzie separate the whole monotone NC hierarchy ? (R. Raz, P. McKenzie, "Separation of the monotone NC hierarchy,")
Michaël Cadilhac
CC BY-SA 2.5
2010-10-31T21:04:28.830Z
A related question: http://cstheory.stackexchange.com/questions/2291/random-monotone-function
Gil Kalai
CC BY-SA 2.5
2010-12-22T14:02:23.853Z
Hello Dai Le. Raz and McKenzie's result is for Boolean monotone circuits, not arithmetic circuits.
Iddo Tzameret
CC BY-SA 2.5
2010-12-22T17:55:19.593Z
@Iddo: Thanks for you clarification! Somehow I misremembered it! My apology to  Michaël.
Dai Le
CC BY-SA 2.5
2010-11-11T15:09:26.333Z
((Don't use $math$ to italicize; use *italics*!))
Jeffε
<cc.complexity-theory><circuit-complexity><barriers><natural-proofs>
Barriers and Monotone Circuit Complexity
Shiva Kintali
# Barriers and Monotone Circuit Complexity

(Asked by: username_0 on 2010-09-20)

[Natural proofs](http://en.wikipedia.org/wiki/Natural_proof) is a barrier towards proving lower bounds on the circuit complexity of boolean functions. They do not directly imply any such barrier in proving lower bounds on the $monotone$ circuit complexity. Is there any progress towards identifying such barriers ? Are there other barriers in the monotone setting ?

**Tags:** cc.complexity-theory, circuit-complexity, barriers, natural-proofs
> **Comments:**
> **username_1**: Didn't Dick Lipton write a post on this a few months ago when discussing natural proofs ? (update): here is the link: http://rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natural-proofs/  
> **username_2**: There are known exponential lower bounds on monotone circuits (Razborov `85, Alon+Boppana `87).  
> **username_0**: I am interested in more recent developments.  
> **username_3**: Didn't Raz and McKenzie separate the whole monotone NC hierarchy ? (R. Raz, P. McKenzie, "Separation of the monotone NC hierarchy,")  
> **username_4**: A related question: http://cstheory.stackexchange.com/questions/2291/random-monotone-function  
> **username_6**: ((Don't use $math$ to italicize; use *italics*!))  
> **username_2**: Hello Dai Le. Raz and McKenzie's result is for Boolean monotone circuits, not arithmetic circuits.  
> **username_5**: @Iddo: Thanks for you clarification! Somehow I misremembered it! My apology to  Michaël.  

---

## 2 answers

### Answer by username_9 on 2010-09-20. Score: 15 | Accepted answer

Benjamin Rossman's recent paper summarises the state of the art for the monotone circuit complexity of k-CLIQUE. In short, Razborov proved a lower bound in 1985, later improved by Alon and Boppana in 1987: $\omega(n^k/(\log n)^k)$, versus the brute force upper bound $O(n^k)$.

Rossman shows a lower bound of $\omega(n^{k/4})$ for the average-case complexity in the Erdős-Rényi model of random graphs; Amano previously showed this was essentially also the upper bound. The quasi-sunflower lemma that forms a key part of the paper is rather neat.

So the natural proofs barrier does not seem to apply to monotone circuit complexity.

Norbert Blum has discussed why lower bounds for monotone circuits are essentially different from circuits with negations. The key observation of Éva Tardos is that a small modification of the [Lovász theta function](http://en.wikipedia.org/wiki/Lov%C3%A1sz_number) has exponential monotone circuit complexity.

* Benjamin Rossman, [*The Monotone Complexity of k-Clique on Random Graphs*](http://www.mit.edu/~brossman/monotone-k-clq.pdf), FOCS 2010.
* Norbert Blum, [*On Negations in Boolean Networks*](http://dx.doi.org/10.1007/978-3-642-03456-5_2), LNCS **5760**, 18–29, 2009.
* É. Tardos, [*The Gap Between Monotone and Non-Monotone Circuit Complexity is Exponential*](http://www.cs.cornell.edu/People/eva/Gap.Between.Monotone.NonMonotone.Circuit.Complexity.is.Exponential.pdf), Combinatorica **8**, 141–142, 1987. [doi:10.1007/BF02122563](http://dx.doi.org/10.1007/BF02122563)

> **Comments:**
> **username_10**: I also found Karchmer's "On proving lower bounds for circuit size" helpful in understanding why monotone circuits are different from circuits with negation.  

---

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

The point is given a general boolean function f there is a monotone boolean function g so that any super linear lower bound on g implies one on f. Or stronger the general complexity of f is equal to the monotone complexity of g up to O(n).

I still am not sure how this relates to the barriers.

> **Comments:**
> **username_8**: Welcome to TCS SE!! Many thanks to your blog posts, it is truly a pleasure to read!  

---

