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:20260405T162342Z
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