The polymorphic gateway between structure and algorithms: Constraint Satisfaction and Beyond

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 appropriate 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 the potential and challenges in extending the polymorphic framework to them. Another interesting connection is with fine-grained complexity, where *partial* polymorphisms govern the runtime of fast exponential-time algorithms for CSPs. 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 (2-2/k)^n time algorithm for k-SAT.

Based on a body of work with Joshua Brakensiek.