BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//hacksw/handcal//NONSGML v1.0//EN
BEGIN:VEVENT
UID:node-12390@prod.cs.cornell.edu
DTSTAMP:20221117T163000Z
DTSTART:20221117T163000Z
DTEND:20221117T173000Z
SUMMARY:When and why do efficient algorithms exist (for constraint satisfaction and beyond)?
DESCRIPTION:Venkatesan Guruswami, University of California Berkeley. When and why do efficient algorithms exist (for constraint satisfaction and beyond)? (via Zoom)Abstract: 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 would be simplistic to hope for a universal theory explaining the underpinnings of easiness/hardness. Yet, in the realm of constraint satisfaction problems, the (recently proved) algebraic dichotomy theorem gives a definitive answer: a polynomial time algorithm exists when there are non-trivial local operations called polymorphisms under which the solution space is closed; otherwise the problem is NP-complete. Inspired and emboldened by this, one might speculate a polymorphic...https://prod.cs.cornell.edu/content/when-and-why-do-efficient-algorithms-exist-constraint-satisfaction-and-beyond
LOCATION:Gates G01 and via Zoom
END:VEVENT
END:VCALENDAR