Injective hardness condition for PCSPs

DOI10.1145/3661814.3662072MaRDI QIDQ6970275zbMATH OpenFDO

Authors Demian Banakh, Marcin Kozik

Publication date 18 June 2025

Full work available at URL https://doi.org/10.1145/3661814.3662072

zbMATH Keywords

algebraic approachconstraint satisfaction problemdichotomypromise constraint satisfaction problem

Mathematics Subject Classification ID

Operations and polynomials in algebraic structures, primal algebras (08A40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07)

Cites work

• (2+)-Sat is NP-hard
• d-to-1 hardness of coloring 3-colorable graphs with o(1) colors
• A dichotomy theorem for nonuniform CSPs
• A Parallel Repetition Theorem
• A proof of the CSP dichotomy conjecture
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Algebraic Approach to Promise Constraint Satisfaction
• CLAP: A New Algorithm for Promise CSPs
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Combinatorial gap theorem and reductions between promise CSPs
• Conditional dichotomy of Boolean ordered promise CSPs
• Conditional Hardness for Approximate Coloring
• Dichotomy for symmetric Boolean PCSPs
• Injective hardness condition for PCSPs
• New hardness results for graph and hypergraph colorings
• On the algebraic structure of combinatorial problems
• On the complexity of H-coloring
• Probabilistic checking of proofs
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• The complexity of 3-colouring \(\mathbf{H}\)-colourable graphs
• The Complexity of Near-Optimal Graph Coloring
• The complexity of promise SAT on non-Boolean domains
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

Cited in

(1)

• Injective hardness condition for PCSPs

This page was built for publication: Injective hardness condition for PCSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6970275)