Xinyao Wang: A journey through constraint satisfication problem.

Abstract

Computational problems exhibit a wide range of behaviors in terms of how efficiently they can be solved. What underlying mathematical structure in a problem enables an efficient algorithm, and what structural obstacles lead to intractability? While one might not expect a universal theory explaining the sources of algorithmic easiness and hardness across all problems, a remarkably clean answer emerges in the setting of constraint satisfaction problems (CSPs). CSPs provide a unifying framework for a broad class of problems. In this talk, we introduce the basic framework of CSP and illustrate it through several classical examples, such as graph coloring, Horn-SAT, and linear equations. We then explain how the complexity of a CSP is governed by certain algebraic operations called polymorphisms, which capture hidden structure in the space of solutions.