BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:When and why do efficient algorithms exist (for constraint satisfa
 ction and beyond)? - Venkatesan Guruswami (UC Berkeley)
DTSTART:20240619T130000Z
DTEND:20240619T140000Z
UID:TALK218104@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:Computational problems exhibit a diverse range of behaviors in
  terms of how quickly and effectively they can be solved.  What underlying
  mathematical structure (or lack thereof) in a computational problem leads
  to an efficient algorithm for solving it (or dictates its intractability)
 ? Given the vast landscape of problems and algorithmic approaches\, it wou
 ld be simplistic to hope for a universal theory explaining the underpinnin
 gs of easiness/hardness. Yet\, in the realm of constraint satisfaction pro
 blems (CSP)\, the algebraic dichotomy theorem gives a definitive answer: a
  polynomial time algorithm exists when there are non-trivial local operati
 ons called polymorphisms under which the solution space is closed\; otherw
 ise the problem is NP-complete. \n\nInspired and emboldened by this\, one 
 might speculate a polymorphic principle in more general contexts\, with sy
 mmetries in the solution space governing efficient algorithms. Beginning w
 ith some background on CSP and the polymorphic approach to understanding t
 heir complexity\, the talk will discuss some extensions beyond CSP where t
 he polymorphic principle seems promising (yet far from understood). In par
 ticular\, we will discuss ``promise CSP'' (PCSP) where one is allowed to s
 atisfy a relaxed version of the constraints (a framework that includes imp
 ortant problems like approximate graph coloring). We will provide glimpses
  of the emerging polymorphic theory characterizing the (in)tractability of
  interesting classes of PCSP as well as the ability of natural classes of 
 algorithms to solve them.
LOCATION:Computer Laboratory\, William Gates Building\, FW26
END:VEVENT
END:VCALENDAR