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.

Intro
Constraint Satisfaction Problems
The Dichotomy Conjecture Theorem
Polymorphisms: example for 2SAI
Approximation Dichotomy Conjecture
Raghavendra's Theorem
Our guess: Abelian Structure
Components
Dictatorship tests
A related analytical question
Techniques
Future Directions: Embeddings Philosophy