15
$\begingroup$

Natural proofs 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 ?

$\endgroup$
8
  • 2
    $\begingroup$ Didn't Dick Lipton write a post on this a few months ago when discussing natural proofs ? (update): here is the link: rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natural-proofs $\endgroup$ Sep 20, 2010 at 2:38
  • 4
    $\begingroup$ There are known exponential lower bounds on monotone circuits (Razborov 85, Alon+Boppana 87). $\endgroup$ Sep 20, 2010 at 3:18
  • 2
    $\begingroup$ Didn't Raz and McKenzie separate the whole monotone NC hierarchy ? (R. Raz, P. McKenzie, "Separation of the monotone NC hierarchy,") $\endgroup$ Sep 20, 2010 at 11:37
  • 1
    $\begingroup$ A related question: cstheory.stackexchange.com/questions/2291/… $\endgroup$
    – Gil Kalai
    Oct 31, 2010 at 21:04
  • 7
    $\begingroup$ ((Don't use $math$ to italicize; use italics!)) $\endgroup$
    – Jeffε
    Nov 11, 2010 at 15:09

2 Answers 2

15
$\begingroup$

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 has exponential monotone circuit complexity.

$\endgroup$
1
  • 1
    $\begingroup$ I also found Karchmer's "On proving lower bounds for circuit size" helpful in understanding why monotone circuits are different from circuits with negation. $\endgroup$
    – Kaveh
    Sep 20, 2010 at 21:29
11
$\begingroup$

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.

$\endgroup$
1
  • 18
    $\begingroup$ Welcome to TCS SE!! Many thanks to your blog posts, it is truly a pleasure to read! $\endgroup$ Dec 18, 2010 at 15:19

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.