BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Memento EPFL// BEGIN:VEVENT SUMMARY:IC Colloquium: Promise Constraint Satisfaction Problems and Width DTSTART:20211108T161500 DTEND:20211108T171500 DTSTAMP:20260407T183542Z UID:9aceff16134d788451b8d305cdc8cc56af5b5eefc09a5b4984ec7e41 CATEGORIES:Conferences - Seminars DESCRIPTION:By: Albert Atserias - Polytechnic University of Catalonia\nVid eo of his talk\n\nAbstract\nGiven 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 th e PCP Theorem. For q = 5\, the problem was also shown NP-hard\, though muc h more recently (2019)\, by enlarging the toolkit with the methods of the algebraic approach to the constraint satisfaction problem. For q = 6 and b eyond\, 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 tha t for any fixed p and q with q >= p\, the problem of distinguishing p-colo rable graphs from graphs that are not even q-colorable is not solvable in sublinear width. This means that the problem cannot be solved by propagati ng constraints that involve less than a sublinear number of vertices in th e graph (we remark that the analogue result for the standard linear and se midefinite programming hierarchies remains open). We obtain this from more general results that we prove on the algebraic structure of promise const raint satisfaction problems (PCSP)\, which in particular imply that the so lution spaces of all fixed-template PCSP that are solvable in sublinear wi dth 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^\\epsi lon-colorings to any given 3-colorable graph\, for any fixed positive epsi lon < 1/2.\n\nThis is based on joint work with Victor Dalmau\, UPF Barcelo na.\n\nBio\nAlbert 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 Pra gue\, in 2008 at the University of California\, Berkeley\, in 2006 and 201 2 at the Isaac Newton Institute for the Mathematical Science in Cambridge and in 2016 at the Simons Institute for the Theory of Computing in Berkele y. His research interests include computational complexity theory\, algori thms\, combinatorics\, and applications of logic to computer science. His works received more than 1500 citations (Google scholar\, 2021). In 2019 h is 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 Foundati ons of Computer Science. This solved a long- standing 20 year-old open pro blem by fully settling he computational complexity of the automatability p roblem for Resolution. In 2015 he won an ERC\nConsolidator Grant (AUTAR)\, leading a team with 3 Phd students and 5 postdoctoral researchers for 5 y ears. 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.\ n\nMore information LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420 STATUS:CONFIRMED END:VEVENT END:VCALENDAR