Symmetric Polymorphisms and Efficient Decidability of Promise CSPs

DOI10.1137/1.9781611975994.18MaRDI QIDQ5146783zbMATH OpenOpenAlexFDO

Authors Joshua Brakensiek, Venkatesan Guruswami

Publication date 2 February 2021

Published in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
• Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• An algorithmic blend of LPs and ring equations for promise CSPs
• Algebraic Approach to Promise Constraint Satisfaction

Cited in

(12)

• Sandwiches for promise constraint satisfaction
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• Dichotomy for symmetric Boolean PCSPs
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• CLAP: A New Algorithm for Promise CSPs
• Topology and Adjunction in Promise Constraint Satisfaction
• SDPs and robust satisfiability of promise CSP
• CLAP: a new algorithm for promise CSPs
• The complexity of promise SAT on non-Boolean domains
• The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
• Symmetric promise constraint satisfaction problems: beyond the Boolean case
• Beyond PCSP (1-in-3, NAE)

This page was built for publication: Symmetric Polymorphisms and Efficient Decidability of Promise CSPs

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