Applications of monotone constraint satisfaction

Computer Science/Discrete Mathematics Seminar II
Topic:Applications of monotone constraint satisfaction
Speaker:Robert Robere
Affiliation:University of Toronto
Date:Tuesday, March 28
Time/Room:10:30am - 12:30pm/S-101
Video Link:

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.