Hard and Easy Constraint Problems - ICBS 2024

Explore the Constraint Satisfaction Problem (CSP) framework and its impact on various combinatorial problems in this 46-minute conference talk by Andrei A. Bulatov at BIMSA. Delve into the connections between CSP and fields such as Logic, Model Theory, Database Theory, and Artificial Intelligence. Examine the complexity of solving general CSPs and discover how restricting constraint languages can lead to efficient solution algorithms. Learn about the long-standing Feder-Vardi conjecture and its significance in determining which constraint languages result in solvable CSPs. Gain insights into the speaker's answer to this open question, which has puzzled researchers since 1978.

Andrei A. Bulatov: Hard and easy constraint problems #ICBS2024