Applications of monotone constraint satisfaction

Recently, a certain "monotone" version of the constraint satisfaction problem has proved an extremely useful tool for attacking problems in circuit, communication, and proof complexity theory. In this talk we discuss this version of the constraint satisfaction problem and touch on its connection to fundamental lower-bounds problems in these areas. We also consider a recent and interesting application: the first exponential lower bounds on the length of cutting planes refutations of random CNF formulas.

This talk is based on joint work with Noah Fleming, Denis Pankratov and Toniann Pitassi. A version of the lower bound theorem has been proven independently by Pavel Hrubeš and Pavel Pudlák.