IC Colloquium: Promise Constraint Satisfaction Problems and Width
Event details
| Date | 08.11.2021 |
| Hour | 16:15 › 17:15 |
| Location | |
| Category | Conferences - Seminars |
| Event Language | English |
By: Albert Atserias - Polytechnic University of Catalonia
Video of his talk
Abstract
Given a 3-colorable graph G with an unknown 3-coloring, how hard is it to find a q-coloring of G when q > 3? For q = 4, the problem was shown NP-hard in the early 1990's as a consequence of the PCP Theorem. For q = 5, the problem was also shown NP-hard, though much more recently (2019), by enlarging the toolkit with the methods of the algebraic approach to the constraint satisfaction problem. For q = 6 and beyond, the best that is known is that the problem would be NP-hard if the so-called 2-to-1 Conjecture with Perfect Completeness were true. We show that the methods of proof complexity of Resolution can be used to show that for any fixed p and q with q >= p, the problem of distinguishing p-colorable graphs from graphs that are not even q-colorable is not solvable in sublinear width. This means that the problem cannot be solved by propagating constraints that involve less than a sublinear number of vertices in the graph (we remark that the analogue result for the standard linear and semidefinite programming hierarchies remains open). We obtain this from more general results that we prove on the algebraic structure of promise constraint satisfaction problems (PCSP), which in particular imply that the solution spaces of all fixed-template PCSP that are solvable in sublinear width are closed under so-called weak near unanimity operations of all large arities. Time permitting, I will also discuss how the study of width for PCSP leads to a new subexponential-time algorithm to find proper n^\epsilon-colorings to any given 3-colorable graph, for any fixed positive epsilon < 1/2.
This is based on joint work with Victor Dalmau, UPF Barcelona.
Bio
Albert Atserias is a Professor of Theoretical Computer Science at UPC. He received a Ph.D. in computer science from UPC in 2002, and a Ph.D. in computer science from University of California, Santa Cruz also in 2002. In 2006 he was a visiting researcher at Charles University in Prague, in 2008 at the University of California, Berkeley, in 2006 and 2012 at the Isaac Newton Institute for the Mathematical Science in Cambridge and in 2016 at the Simons Institute for the Theory of Computing in Berkeley. His research interests include computational complexity theory, algorithms, combinatorics, and applications of logic to computer science. His works received more than 1500 citations (Google scholar, 2021). In 2019 his paper "Automating Resolution is NP-Hard", joint with Moritz Müller, was a co-winner of the Best Paper Award at IEEE 60th Symposium on Foundations of Computer Science. This solved a long- standing 20 year-old open problem by fully settling he computational complexity of the automatability problem for Resolution. In 2015 he won an ERC
Consolidator Grant (AUTAR), leading a team with 3 Phd students and 5 postdoctoral researchers for 5 years. He was invited as plenary speaker of ASL Logic Colloquium (2007 and 2018), the CSL (2004), LICS (2011), SAT (2013), FSTTCS (2020), and at upcoming ICALP (2022), as well as Oberwolfach, BIRS, Simons Institute at Berkeley, and Dagstuhl, several times. He has served in the editorial board of journals ACM TOCL and ACM TOCT and Information and Computation.
More information
Video of his talk
Abstract
Given a 3-colorable graph G with an unknown 3-coloring, how hard is it to find a q-coloring of G when q > 3? For q = 4, the problem was shown NP-hard in the early 1990's as a consequence of the PCP Theorem. For q = 5, the problem was also shown NP-hard, though much more recently (2019), by enlarging the toolkit with the methods of the algebraic approach to the constraint satisfaction problem. For q = 6 and beyond, the best that is known is that the problem would be NP-hard if the so-called 2-to-1 Conjecture with Perfect Completeness were true. We show that the methods of proof complexity of Resolution can be used to show that for any fixed p and q with q >= p, the problem of distinguishing p-colorable graphs from graphs that are not even q-colorable is not solvable in sublinear width. This means that the problem cannot be solved by propagating constraints that involve less than a sublinear number of vertices in the graph (we remark that the analogue result for the standard linear and semidefinite programming hierarchies remains open). We obtain this from more general results that we prove on the algebraic structure of promise constraint satisfaction problems (PCSP), which in particular imply that the solution spaces of all fixed-template PCSP that are solvable in sublinear width are closed under so-called weak near unanimity operations of all large arities. Time permitting, I will also discuss how the study of width for PCSP leads to a new subexponential-time algorithm to find proper n^\epsilon-colorings to any given 3-colorable graph, for any fixed positive epsilon < 1/2.
This is based on joint work with Victor Dalmau, UPF Barcelona.
Bio
Albert Atserias is a Professor of Theoretical Computer Science at UPC. He received a Ph.D. in computer science from UPC in 2002, and a Ph.D. in computer science from University of California, Santa Cruz also in 2002. In 2006 he was a visiting researcher at Charles University in Prague, in 2008 at the University of California, Berkeley, in 2006 and 2012 at the Isaac Newton Institute for the Mathematical Science in Cambridge and in 2016 at the Simons Institute for the Theory of Computing in Berkeley. His research interests include computational complexity theory, algorithms, combinatorics, and applications of logic to computer science. His works received more than 1500 citations (Google scholar, 2021). In 2019 his paper "Automating Resolution is NP-Hard", joint with Moritz Müller, was a co-winner of the Best Paper Award at IEEE 60th Symposium on Foundations of Computer Science. This solved a long- standing 20 year-old open problem by fully settling he computational complexity of the automatability problem for Resolution. In 2015 he won an ERC
Consolidator Grant (AUTAR), leading a team with 3 Phd students and 5 postdoctoral researchers for 5 years. He was invited as plenary speaker of ASL Logic Colloquium (2007 and 2018), the CSL (2004), LICS (2011), SAT (2013), FSTTCS (2020), and at upcoming ICALP (2022), as well as Oberwolfach, BIRS, Simons Institute at Berkeley, and Dagstuhl, several times. He has served in the editorial board of journals ACM TOCL and ACM TOCT and Information and Computation.
More information
Practical information
- General public
- Free
- This event is internal
Contact
- Host: Mika Göös