Michael Roman (University of Illinois, Urbana-Champaign):
A survey of some monotone complexity lower bounds

A function f: {0,1}^n -> {0,1} is monotone if increasing the value of any input bit doesn't decrease the value of the function. It turns out that any monotone function can be computed by a circuit using only AND and OR gates (no NOT gates). The monotone circuit complexity of a monotone function is the size of the smallest such circuit. Razborov proved that deciding whether or not a graph has a large clique has superpolynomial monotone circuit complexity. We shall sketch the proof of Razborov's theorem and mention some related results.