Algebraic and algorithmic synergies between promise and infinite-domain CSPs
Antoine Mottet
Abstract
We establish a framework that allows us to transfer results between some constraint satisfaction problems with infinite templates and promise constraint satisfaction problems. On the one hand, we obtain new algebraic results for infinite-domain CSPs giving new criteria for NP-hardness. On the other hand, we show the existence of promise CSPs with finite templates that reduce naturally to tractable infinite-domain CSPs in the scope of the Bodirsky-Pinsker conjecture, but that are not finitely tractable, thereby showing a non-trivial connection between those two fields of research. In an important part of our proof, we also obtain uniform polynomial-time algorithms solving temporal constraint satisfaction problems.
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.
3 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
- New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs cites Hierarchies of Minion Tests for PCSPs through Tensors
- Ineffectiveness for Search and Undecidability of PCSP Meta-Problems cites Local consistency as a reduction between constraint satisfaction problems
- Ineffectiveness for Search and Undecidability of PCSP Meta-Problems cites Promise Constraint Satisfaction and Width
- Ineffectiveness for Search and Undecidability of PCSP Meta-Problems cites Hierarchies of Minion Tests for PCSPs through Tensors
- Local consistency as a reduction between constraint satisfaction problems cites Hierarchies of Minion Tests for PCSPs through Tensors
- Hierarchies of Minion Tests for PCSPs through Tensors cites Local consistency as a reduction between constraint satisfaction problems
- Hierarchies of Minion Tests for PCSPs through Tensors cites Promise Constraint Satisfaction and Width
Cited by top-tier papers3
- Hierarchies of Minion Tests for PCSPs through TensorsLorenzo Ciardo, Stanislav ZivnýSODA 2023 · 13 citations
- New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPsJoshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Potechin et al.SODA 2026 · 2 citations
- Ineffectiveness for Search and Undecidability of PCSP Meta-ProblemsAlberto LarrauriFOCS 2025
Builds on4
- Local consistency as a reduction between constraint satisfaction problemsVíctor Dalmau, Jakub OprsalLICS 2024 · 15 citations
- Hierarchies of Minion Tests for PCSPs through TensorsLorenzo Ciardo, Stanislav ZivnýSODA 2023 · 13 citations
- Smooth approximations and CSPs over finitely bounded homogeneous structuresAntoine Mottet, Michael PinskerLICS 2022 · 6 citations
- Promise Constraint Satisfaction and WidthAlbert Atserias, Víctor DalmauSODA 2022
Related papers
- Decidability of InterpretabilityRoman Feller, Michael PinskerLICS 2026
- Temporal Constraint Satisfaction Problems in Fixed-Point LogicManuel Bodirsky, Wied Pakusa, Jakub RydvalLICS 2020 · 10 citations
- Injective hardness condition for PCSPsDemian Banakh, Marcin KozikLICS 2024 · 1 citation
- Solving Infinite-Domain CSPs Using the Patchwork PropertyKonrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George OsipovAAAI 2021 · 5 citations
- Combinatorial Gap Theorem and Reductions between Promise CSPsLibor Barto, Marcin KozikSODA 2022 · 15 citations
