*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC)
Venkat Guruswami
Monday, December 3, 2018
Klaus 1116E - 11:00 am
Title: The polymorphic gateway between structure and algorithms: Beyond CSPs
Abstract: What underlying mathematical structure (or lack thereof) in a computational problem governs its efficient solvability (or dictates its hardness)? In the realm of constraint satisfaction problems (CSPs), the 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 broader polymorphic principle: if there are interesting ways to combine solutions to get more solutions, then the problem ought to be tractable (with context dependent interpretations of "interesting" and "tractable”).
Beginning with some background on the polymorphic approach to understanding the complexity of constraint satisfaction, the talk will discuss some extensions beyond CSPs where the polymorphic principle seems promising (yet far from understood). Specifically, we will discuss promise CSPs where one is allowed to satisfy a relaxed version of the constraints (a framework that includes important problems like approximate graph coloring and discrepancy minimization), and the potential and challenges in applying the polymorphic framework to them. Another interesting direction is fine-grained complexity, where partial polymorphisms govern the runtime of fast exponential-time algorithms. Our inquiries into these directions also reveal some interesting connections to optimization, such as algorithms to solve LPs over different rings (like integers adjoined with sqrt{2}), and a random-walk based algorithm interpolating between 0-1 and linear programming, generalizing Schöning's famous (4/3)^n time algorithm for 3-SAT.
Based on a body of work with Joshua Brakensiek.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
