Promise constraint satisfaction and width

DOI10.1137/1.9781611977073.48MaRDI QIDQ6575121zbMATH OpenFDO

Authors Albert Atserias, Víctor Dalmau

Publication date 19 July 2024

Full work available at URL https://doi.org/10.1137/1.9781611977073.48

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(12)

• Promise and infinite-domain constraint satisfaction
• Quantum advantage and CSP complexity
• Solving promise equations over monoids and groups
• Approximate graph coloring and the crystal with a hollow shadow
• 1-in-3 vs. not-all-equal: dichotomy of a broken promise
• Quantum advantage and CSP complexity
• Semidefinite programming and linear equations vs. homomorphism problems
• 1-in-3 vs. not-all-equal: dichotomy of a broken promise
• On the complexity of symmetric vs. functional PCSPs
• Solving promise equations over monoids and groups
• The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
• Undefinability of approximation of 2-to-2 games

This page was built for publication: Promise constraint satisfaction and width

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