Pure Math Colloquium

Michael Pinsker, Technische Universität Wien / Charles University Prague

"Algebraic, logical, and combinatorial methods for Constraint Satisfaction Problems"

Constraint Satisfaction Problems (CSPs) are a kind of computational problem where one is given a finite number of variables along with "constraints" about these variables; the problem is to decide whether or not the variables can be assigned values such that all constraints are satisfied. An example of a CSP is solving equations over a fixed field. The complexity of a CSP depends on the range of the possible values for the variables (e.g., the rational numbers, a finite field,...) and the type of constraints allowed (e.g., any equation, linear equations,...). If this range is finite, then the CSP is either solvable in polynomial time or NP-complete, by a recent theorem of Bulatov and Zhuk which answered a conjecture that had lasted 25 years. I am going to discuss the general algebraic approach used in their proofs, as well as the additional methods from model theory and Ramsey theory required to investigate CSPs if the range is infinite.

Zoom meeting: https://zoom.us/j/93240216981?pwd=aE0vbktRV1NvMTFzbFVaalVpb1pCdz09