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.
Overview
Syllabus
Andrei A. Bulatov: Hard and easy constraint problems #ICBS2024
Taught by
BIMSA
Related Courses
-
When and How are Promise Constraint Satisfaction Problems Efficiently Solvable
-
Constraint Satisfaction Problems - Lecture 20b of CS Theory Toolkit
-
Constraint Satisfaction Problem - What Makes the Problem Easy
-
Constraint Satisfaction Problems: Consistency Algorithms - Part 6
-
The Complexity of Satisfiable CSPs
-
Local Weak Convergence for Random Constraint Satisfaction Problems
