Lune

SODA2020Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

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
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers8

  1. Hierarchies of Minion Tests for PCSPs through TensorsLorenzo Ciardo, Stanislav ZivnýSODA 2023 · 13 citations
  2. Approximate Graph Colouring and CrystalsLorenzo Ciardo, Stanislav ZivnýSODA 2023 · 9 citations
  3. SDPs and Robust Satisfiability of Promise CSPJoshua Brakensiek, Venkatesan Guruswami, Sai SandeepSTOC 2023 · 8 citations
  4. CLAP: A New Algorithm for Promise CSPsLorenzo Ciardo, Stanislav ZivnýSODA 2022 · 5 citations
  5. Semidefinite Programming and Linear Equations vs. Homomorphism ProblemsLorenzo Ciardo, Stanislav ZivnýSTOC 2024 · 4 citations

Builds on1

  1. Improved hardness for H-colourings of G-colourable graphsMarcin Wrochna, Stanislav ZivnýSODA 2020 · 19 citations

Related papers

  1. A Categorical Perspective on Constraint Satisfaction: The Wonderland of AdjunctionsMaximilian Hadek, Tomás Jakl, Jakub OprsalLICS 2026
  2. 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
  3. Promise Constraint Satisfaction and WidthAlbert Atserias, Víctor DalmauSODA 2022
  4. Boolean symmetric vs. functional PCSP dichotomyTamio-Vesa Nakajima, Stanislav ZivnýLICS 2023 · 5 citations
  5. Efficient Algorithms and New Characterizations for CSP SparsificationSanjeev Khanna, Aaron Putterman, Madhu SudanSTOC 2025 · 12 citations
Dusk over the sea between two cliffs drawn in fine vertical lines