The Complexity of Satisfiable CSPs

Explore a lecture on the complexity of satisfiable Constraint Satisfaction Problems (CSPs) delivered by Dor Minzer at the Workshop on Tensors: Quantum Information, Complexity and Combinatorics. Delve into a recent line of research aimed at proving a dichotomy theorem for CSPs in the realm of approximation problems. Examine the connections to other fields such as discrete Fourier analysis, direct product testing, and linearity testing. Learn about the Dichotomy Conjecture Theorem, polymorphisms, Raghavendra's Theorem, and the concept of Abelian Structure. Investigate dictatorship tests, related analytical questions, and techniques used in this field. Gain insights into future directions, including the Embeddings Philosophy. This 44-minute talk, presented in French, offers a comprehensive overview of current research in CSP complexity.