Speaker:

Xinyao Wang (University of Electronic Science and Technology of China)

Time:

• 16:20-17:20 (Time in Beijing)
• March 13, 2026 (Friday)

Venue:

518, Research Building 4

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.