BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20240331T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20241027T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20241106T202404Z
UID:666826f557be0930623296@ist.ac.at
DTSTART:20240701T110000
DTEND:20240701T120000
DESCRIPTION:Speaker: Venkatesan Guruswami\nhosted by Marco Mondelli\nAbstra
ct: Computational problems exhibit a diverse range of behaviors in terms o
f how quickly and effectively they can be solved. What underlying mathemat
ical structure (or lack thereof) in a computational problem leads to an ef
ficient algorithm for solving it (or dictates its intractability)? Given t
he vast landscape of problems and algorithmic approaches\, it would be sim
plistic to hope for a universal theory explaining the underpinnings of eas
iness/hardness. Yet\, in the realm of constraint satisfaction problems (CS
P)\, the algebraic dichotomy theorem gives a definitive answer: a polynomi
al time algorithm exists when there are non-trivial local operations calle
d polymorphisms under which the solution space is closed\; otherwise the p
roblem is NP-complete.Inspired and emboldened by this\, one might speculat
e a polymorphic principle in more general contexts\, with symmetries in th
e solution space governing efficient algorithms. Beginning with some backg
round on CSP and the polymorphic approach to understanding their complexit
y\, the talk will discuss some extensions beyond CSP where the polymorphic
principle seems promising (yet far from understood). In particular\, we w
ill discuss promise CSP'' (PCSP) where one is allowed to satisfy a relaxed
version of the constraints (a framework that includes important problems
like approximate graph coloring). We will provide glimpses of the emerging
polymorphic theory characterizing the (in)tractability of interesting cla
sses of PCSP as well as the ability of natural classes of algorithms to so
lve them.
LOCATION:Office Bldg West / Ground floor / Heinzel Seminar Room (I21.EG.101
)\, ISTA
ORGANIZER:jdeanton@ist.ac.at
SUMMARY:Venkatesan Guruswami: When and why do efficient algorithms exist (f
or constraint satisfaction and beyond)?
URL:https://talks-calendar.ista.ac.at/events/5072
END:VEVENT
END:VCALENDAR