15

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 ?

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Shiva Kintali
  • 10,578
  • 41
  • 74

2 Answers2

15

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.

András Salamon
  • 19,000
  • 3
  • 64
  • 150
  • 1
    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 Sep 20 '10 at 21:29
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.

dick lipton
  • 451
  • 4
  • 4