Proof complexity of constraint satisfaction problems

Prelegent(ci)

Joanna Ochremiak

Afiliacja

Universite Paris Diderot

Termin

12 kwietnia 2017 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Albert Atserias

Seminarium

Seminarium „Teoria automatów”

---

In this talk I will define a few "popular" proof systems and argue that constraint satisfaction problems which admit small size refutations in those proof systems are exactly the constraint satisfaction problems which can be solved by local consistency methods.

---