Lune

LICS2024Top-tier venue

Injective hardness condition for PCSPs

Demian Banakh, Marcin Kozik

Abstract

We present a template for the Promise Constraint Satisfaction Problem (PCSP) which is NP-hard but does not satisfy the current state-of-the-art hardness condition [ACMTCT'21]. We introduce a new "injective" condition based on the smooth version of the layered PCP Theorem and use this new condition to confirm that the problem is indeed NP-hard.

In the second part of the article, we establish a dichotomy for Boolean PCSPs defined by templates with polymorphisms in the set of linear threshold functions. The reasoning relies on the new injective condition.

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.

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

  • New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs cites CLAP: A New Algorithm for Promise CSPs
  • New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs cites Combinatorial Gap Theorem and Reductions between Promise CSPs
  • Ineffectiveness for Search and Undecidability of PCSP Meta-Problems cites CLAP: A New Algorithm for Promise CSPs
  • Ineffectiveness for Search and Undecidability of PCSP Meta-Problems cites Combinatorial Gap Theorem and Reductions between Promise CSPs
  • Ineffectiveness for Search and Undecidability of PCSP Meta-Problems cites Local consistency as a reduction between constraint satisfaction problems
  • On the Usefulness of Promises cites Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
  • Local consistency as a reduction between constraint satisfaction problems cites Combinatorial Gap Theorem and Reductions between Promise CSPs
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPsJoshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Potechin et al.SODA 2026 · 2 citations
  2. Ineffectiveness for Search and Undecidability of PCSP Meta-ProblemsAlberto LarrauriFOCS 2025
  3. On the Usefulness of PromisesPer Austrin, Johan Håstad, Björn MartinssonSODA 2026

Builds on3

  1. Combinatorial Gap Theorem and Reductions between Promise CSPsLibor Barto, Marcin KozikSODA 2022 · 15 citations
  2. Local consistency as a reduction between constraint satisfaction problemsVíctor Dalmau, Jakub OprsalLICS 2024 · 15 citations
  3. CLAP: A New Algorithm for Promise CSPsLorenzo Ciardo, Stanislav ZivnýSODA 2022 · 5 citations

Related papers

  1. Algebraic and algorithmic synergies between promise and infinite-domain CSPsAntoine MottetLICS 2025 · 1 citation
  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. Binary symmetries of tractable non-rigid structuresPaolo Marimon, Michael PinskerLICS 2025 · 3 citations
  4. Boolean symmetric vs. functional PCSP dichotomyTamio-Vesa Nakajima, Stanislav ZivnýLICS 2023 · 5 citations
  5. SDPs and Robust Satisfiability of Promise CSPJoshua Brakensiek, Venkatesan Guruswami, Sai SandeepSTOC 2023 · 8 citations
Dusk over the sea between two cliffs drawn in fine vertical lines