Lune

LICS2024Top-tier venue

Local consistency as a reduction between constraint satisfaction problems

Víctor Dalmau, Jakub Oprsal

Abstract

We study the use of local consistency methods as reductions between constraint satisfaction problems (CSPs), and promise version thereof, with the aim to classify these reductions in a similar way as the algebraic approach classifies gadget reductions between CSPs. This research is motivated by the requirement of more expressive reductions in the scope of promise CSPs. While gadget reductions are enough to provide all necessary hardness in the scope of (finite domain) non-promise CSP, in promise CSPs a wider class of reductions needs to be used.

We provide a general framework of reductions, which we call consistency reductions, that covers most (if not all) reductions recently used for proving NP-hardness of promise CSPs. We prove some basic properties of these reductions, and provide the first steps towards understanding the power of consistency reductions by characterizing a fragment associated to arc-consistency in terms of polymorphisms of the template. In addition to showing hardness, consistency reductions can also be used to provide feasible algorithms by reducing to a fixed tractable (promise) CSP, for example, to solving systems of affine equations. In this direction, among other results, we describe the well-known Sherali-Adams hierarchy for CSP in terms of a consistency reduction to linear programming.

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.

10 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

  • Injective hardness condition for PCSPs cites Combinatorial Gap Theorem and Reductions between Promise CSPs
  • Combinatorial Gap Theorem and Reductions between Promise CSPs cites Improved hardness for H-colourings of G-colourable graphs
  • How Random CSPs Fool Hierarchies: II cites Semidefinite Programming and Linear Equations vs. Homomorphism Problems
  • How Random CSPs Fool Hierarchies: II cites Hierarchies of Minion Tests for PCSPs through Tensors
  • Hierarchies of Minion Tests for PCSPs through Tensors cites How Random CSPs Fool Hierarchies: II
  • How Random CSPs Fool Hierarchies: II cites Approximate Graph Colouring and the Hollow Shadow
  • Algebraic and algorithmic synergies between promise and infinite-domain CSPs cites Hierarchies of Minion Tests for PCSPs through Tensors
  • Hierarchies of Minion Tests for PCSPs through Tensors cites Algebraic and algorithmic synergies between promise and infinite-domain CSPs
  • Semidefinite Programming and Linear Equations vs. Homomorphism Problems cites Hierarchies of Minion Tests for PCSPs through Tensors
  • Semidefinite Programming and Linear Equations vs. Homomorphism Problems cites Approximate Graph Colouring and the Hollow Shadow
  • Hierarchies of Minion Tests for PCSPs through Tensors cites Combinatorial Gap Theorem and Reductions between Promise CSPs
  • Approximate Graph Colouring and the Hollow Shadow cites Combinatorial Gap Theorem and Reductions between Promise CSPs
  • Approximate Graph Colouring and the Hollow Shadow 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 papers10

  1. Hierarchies of Minion Tests for PCSPs through TensorsLorenzo Ciardo, Stanislav ZivnýSODA 2023 · 13 citations
  2. Semidefinite Programming and Linear Equations vs. Homomorphism ProblemsLorenzo Ciardo, Stanislav ZivnýSTOC 2024 · 4 citations
  3. Injective hardness condition for PCSPsDemian Banakh, Marcin KozikLICS 2024 · 1 citation
  4. How Random CSPs Fool Hierarchies: IISiu On Chan, Hiu Tsun NgSTOC 2025 · 1 citation
  5. Algebraic and algorithmic synergies between promise and infinite-domain CSPsAntoine MottetLICS 2025 · 1 citation

Builds on8

  1. Improved hardness for H-colourings of G-colourable graphsMarcin Wrochna, Stanislav ZivnýSODA 2020 · 19 citations
  2. Combinatorial Gap Theorem and Reductions between Promise CSPsLibor Barto, Marcin KozikSODA 2022 · 15 citations
  3. Hierarchies of Minion Tests for PCSPs through TensorsLorenzo Ciardo, Stanislav ZivnýSODA 2023 · 13 citations
  4. Approximate Graph Colouring and the Hollow ShadowLorenzo Ciardo, Stanislav ZivnýSTOC 2023 · 13 citations
  5. Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSPLibor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik et al.LICS 2021 · 6 citations

Related papers

  1. Lower Bounds for CSP Hierarchies Through Ideal ReductionJonas Conneryd, Yassine Ghannane, Shuo PangSODA 2026
  2. A Categorical Perspective on Constraint Satisfaction: The Wonderland of AdjunctionsMaximilian Hadek, Tomás Jakl, Jakub OprsalLICS 2026
  3. Promise Constraint Satisfaction and WidthAlbert Atserias, Víctor DalmauSODA 2022
  4. SDPs and Robust Satisfiability of Promise CSPJoshua Brakensiek, Venkatesan Guruswami, Sai SandeepSTOC 2023 · 8 citations
  5. Towards Infinite PCSP: A Dichotomy for Monochromatic CliquesDemian Banakh, Alexey Barsukov, Tamio-Vesa NakajimaLICS 2026
Dusk over the sea between two cliffs drawn in fine vertical lines