You are not logged in | Log in
Logo of the Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw Logo of the Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw

joint work with Albert Atserias

Speaker(s)
Joanna Ochremiak
Affiliation
Universite Paris Diderot
Date
April 12, 2017, 2:15 p.m.
Room
room 5870
Title in Polish
Proof complexity of constraint satisfaction problems
Seminar
Seminar Automata Theory

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.

Careers

Website

© 2024 University of Warsaw. All rights reserved.