Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
Joshua Brakensiek, Venkatesan Guruswami
Abstract
In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not being able to satisfy all the weak constraints. The most commonly cited example of a promise CSP is the approximate graph coloring problem-which has recently seen exciting progress [BKO19, WŽ20] benefiting from a systematic algebraic approach to promise CSPs based on "polymorphisms," operations that map tuples in the strict form of each constraint to tuples in the corresponding weak form.
In this work, we present a simple algorithm which in polynomial time solves the decision problem for all promise CSPs that admit infinitely many symmetric polymorphisms, which are invariant under arbitrary coordinate permutations. This generalizes previous work of the first two authors [BG19]. We also extend this algorithm to a more general class of blocksymmetric polymorphisms. As a corollary, this single algorithm solves all polynomial-time tractable Boolean CSPs simultaneously. These results give a new perspective on Schaefer's classic dichotomy theorem and shed further light on how symmetries of polymorphisms enable algorithms. Finally, we show that block symmetric polymorphisms are not only sufficient but also necessary for this algorithm to work, thus establishing its precise power.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
8 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Approximate Graph Colouring and Crystals cites CLAP: A New Algorithm for Promise CSPs
- Approximate Graph Colouring and Crystals cites Improved hardness for H-colourings of G-colourable graphs
- Approximate Graph Colouring and Crystals cites Hierarchies of Minion Tests for PCSPs through Tensors
- CLAP: A New Algorithm for Promise CSPs cites Improved hardness for H-colourings of G-colourable graphs
- CLAP: A New Algorithm for Promise CSPs cites Hierarchies of Minion Tests for PCSPs through Tensors
- Hierarchies of Minion Tests for PCSPs through Tensors cites CLAP: A New Algorithm for Promise CSPs
- SDPs and Robust Satisfiability of Promise CSP cites CLAP: A New Algorithm for Promise CSPs
- SDPs and Robust Satisfiability of Promise CSP cites Hierarchies of Minion Tests for PCSPs through Tensors
- Hierarchies of Minion Tests for PCSPs through Tensors cites SDPs and Robust Satisfiability of Promise CSP
- Semidefinite Programming and Linear Equations vs. Homomorphism Problems cites Approximate Graph Colouring and Crystals
- Semidefinite Programming and Linear Equations vs. Homomorphism Problems cites CLAP: A New Algorithm for Promise CSPs
- Semidefinite Programming and Linear Equations vs. Homomorphism Problems cites SDPs and Robust Satisfiability of Promise CSP
- Semidefinite Programming and Linear Equations vs. Homomorphism Problems cites Hierarchies of Minion Tests for PCSPs through Tensors
Cited by top-tier papers8
- Hierarchies of Minion Tests for PCSPs through TensorsLorenzo Ciardo, Stanislav ZivnýSODA 2023 · 13 citations
- Approximate Graph Colouring and CrystalsLorenzo Ciardo, Stanislav ZivnýSODA 2023 · 9 citations
- SDPs and Robust Satisfiability of Promise CSPJoshua Brakensiek, Venkatesan Guruswami, Sai SandeepSTOC 2023 · 8 citations
- CLAP: A New Algorithm for Promise CSPsLorenzo Ciardo, Stanislav ZivnýSODA 2022 · 5 citations
- Semidefinite Programming and Linear Equations vs. Homomorphism ProblemsLorenzo Ciardo, Stanislav ZivnýSTOC 2024 · 4 citations
Builds on1
Related papers
- A Categorical Perspective on Constraint Satisfaction: The Wonderland of AdjunctionsMaximilian Hadek, Tomás Jakl, Jakub OprsalLICS 2026
- 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promiseLorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima et al.LICS 2024 · 2 citations
- Promise Constraint Satisfaction and WidthAlbert Atserias, Víctor DalmauSODA 2022
- Boolean symmetric vs. functional PCSP dichotomyTamio-Vesa Nakajima, Stanislav ZivnýLICS 2023 · 5 citations
- Efficient Algorithms and New Characterizations for CSP SparsificationSanjeev Khanna, Aaron Putterman, Madhu SudanSTOC 2025 · 12 citations
