BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Peter Mayr (CU Boulder)
DTSTART:20210928T190000Z
DTEND:20210928T200000Z
DTSTAMP:20260423T004727Z
UID:PALS/12
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/PALS/12/">So
 lving small PCSPs via large CSPs</a>\nby Peter Mayr (CU Boulder) as part o
 f PALS Panglobal Algebra and Logic Seminar\n\n\nAbstract\nFor relational s
 tructures A\, B\, the Promise Constraint Satisfaction Problem PCSP(A\, B) 
 asks whether a given input structure maps homomorphically to A or does not
  even map to B. We are promised that the input satisfies exactly one of th
 ese two cases.\nNote that if there exists C with homomorphisms A → C →
  B\, then PCSP(A\, B) reduces to CSP(C). All known tractable PCSPs seem to
  reduce to tractable CSPs in this way. However Barto (2019) showed that so
 me PCSPs over finite structures require solving CSPs over infinite C. We p
 rovide examples showing that even when a reduction to finite C is possible
 \, this structure may become arbitrarily large.\nThis is joint work with A
 lexandr Kazda and Dmitriy Zhuk.\n
LOCATION:https://researchseminars.org/talk/PALS/12/
END:VEVENT
END:VCALENDAR