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.