BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Kristina Asimi (Charles University Prague) DTSTART:20210223T200000Z DTEND:20210223T210000Z DTSTAMP:20260423T021528Z UID:PALS/2 DESCRIPTION:Title: Fin itely tractable PCSPs\nby Kristina Asimi (Charles University Prague) a s part of PALS Panglobal Algebra and Logic Seminar\n\n\nAbstract\nThe Prom ise Constraint Satisfaction Problem (PCSP) is a generalization of the Cons traint Satisfaction Problem (CSP). In a [LICS '19] paper it was shown that a specific PCSP\, the problem to find a valid Not-All-Equal solution to a 1-in-3-SAT instance\, is not finitely tractable in that it can be solved by a trivial reduction to a tractable CSP\, but such a CSP is necessarily over an infinite domain (unless P=NP). We further explore this phenomenon: we give a general necessary condition for finite tractability and charact erize finite tractability within a class of templates - the "basic" tracta ble cases in the dichotomy theorem for symmetric Boolean PCSPs allowing ne gations by Brakensiek and Guruswami [SODA'18]. This is a joint work with L ibor Barto.\n LOCATION:https://researchseminars.org/talk/PALS/2/ END:VEVENT END:VCALENDAR