Spring 2021

Fellows Talk

Thursday, Apr. 15, 2021 11:00 am12:00 pm PDT

Add to Calendar


Joanna Ochremiak (CNRS)



Speaker: Joanna Ochremiak (CNRS)

TitleProof Complexity of Constraint Satisfaction Problems

Abstract: Many natural computational problems, such as satisfiability and solving systems of equations, can be expressed in a unified way as constraint satisfaction problems (CSPs). In this talk I will show that, for the most studied propositional and semi-algebraic proof systems, the usual reductions preserving the complexity of the constraint satisfaction problem preserve also its proof complexity. As an application, I will present gap theorems, which say that CSPs that admit small size refutations in some classical proof systems are exactly the constraint satisfaction problems of bounded width. This is joint work with Albert Atserias.