A proof of CSP dichotomy conjecture

DOI10.1109/FOCS.2017.38MaRDI QIDQ6946350zbMATH OpenFDO

Authors D. N. Zhuk

Publication date 6 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2017.38

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(30)

• Ivo G. Rosenberg's work on maximal clones and minimal clones
• The complexity of promise constraint satisfaction problem seen from the other side
• Hrushovski's encoding and -categorical CSP monsters
• Complexity of finite Borel asymptotic dimension
• Promise and infinite-domain constraint satisfaction
• Network satisfaction problems solved by k-consistency
• Homogeneity and homogenizability: hard problems for the logic SNP
• An order out of nowhere: a new algorithm for infinite-domain CSPs
• _2P vs PSpace dichotomy for the quantified constraint satisfaction problem
• When do homomorphism counts help in query algorithms?
• A characterization of efficiently compilable constraint languages
• Approximate graph coloring and the crystal with a hollow shadow
• The generic circular triangle-free graph
• The complexity of resilience problems via valued constraint satisfaction problems
• Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures
• A complexity dichotomy in spatial reasoning via Ramsey theory
• On the mysteries of MAX NAE-SAT
• Sketching approximability of all finite CSPs
• The complexity of the distributed constraint satisfaction problem
• Symmetric linear arc monadic Datalog and gadget reductions
• Datalog-expressibility for monadic and guarded second-order logic
• Smooth approximations and relational width collapses
• Symmetric linear arc monadic Datalog and gadget reductions
• Clones of Borel Boolean functions
• The ideal membership problem and abelian groups
• Temporal valued constraint satisfaction problems
• Three fundamental questions in modern infinite-domain constraint satisfaction
• On the degree automatability of sum-of-squares proofs
• Satisfiability of commutative vs. non-commutative CSPs
• The role of regularity in (hyper-)clique detection and implications for optimizing Boolean CSPs

This page was built for publication: A proof of CSP dichotomy conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6946350)