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$
  • 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$ – Suresh Venkat Sep 20 '10 at 2:38
  • 4
    $\begingroup$ There are known exponential lower bounds on monotone circuits (Razborov 85, Alon+Boppana 87). $\endgroup$ – Iddo Tzameret Sep 20 '10 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$ – Michaël Cadilhac Sep 20 '10 at 11:37
  • 1
    $\begingroup$ A related question: cstheory.stackexchange.com/questions/2291/… $\endgroup$ – Gil Kalai Oct 31 '10 at 21:04
  • 7
    $\begingroup$ ((Don't use $math$ to italicize; use italics!)) $\endgroup$ – Jeffε Nov 11 '10 at 15:09
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
    $\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 '10 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$
  • 18
    $\begingroup$ Welcome to TCS SE!! Many thanks to your blog posts, it is truly a pleasure to read! $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 18 '10 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.