Barriers and Monotone Circuit Complexity
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