Barriers and Monotone Circuit Complexity

Question

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 ?

Answer 1

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.

• Benjamin Rossman, The Monotone Complexity of k-Clique on Random Graphs, FOCS 2010.
• Norbert Blum, On Negations in Boolean Networks, LNCS 5760, 18–29, 2009.
• É. Tardos, The Gap Between Monotone and Non-Monotone Circuit Complexity is Exponential, Combinatorica 8, 141–142, 1987. doi:10.1007/BF02122563

Answer 2

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.