Local consistency as a reduction between constraint satisfaction problems
From MaRDI portal
Cites work
- (2+)-Sat is NP-hard
- d-to-1 hardness of coloring 3-colorable graphs with o(1) colors
- \(n\)-permutability and linear Datalog implies symmetric Datalog
- A dichotomy theorem for nonuniform CSPs
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A proof of the CSP dichotomy conjecture
- Affine systems of equations and counting infinitary logic
- Algebraic Approach to Promise Constraint Satisfaction
- Approximate graph colouring and the hollow shadow
- Boolean symmetric vs. functional PCSP dichotomy
- Bounded width problems and algebras
- Classifying the Complexity of Constraints Using Finite Algebras
- Closure properties of constraints
- Cohomology in constraint satisfaction and structure isomorphism
- Combinatorial gap theorem and reductions between promise CSPs
- Conjunctive-query containment and constraint satisfaction
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Dichotomy for symmetric Boolean PCSPs
- Dualities for Constraint Satisfaction Problems
- Handbook of constraint programming.
- Hierarchies of Minion Tests for PCSPs through Tensors
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Improved hardness for \(H\)-colourings of \(G\)-colourable graphs
- Improved hardness of approximating chromatic number
- Limitations of algebraic approaches to graph isomorphism testing
- Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
- Probabilistic checking of proofs
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Symmetries of graphs and structures that fail to interpret a finite thing
- The complexity of 3-colouring \(\mathbf{H}\)-colourable graphs
- The complexity of promise SAT on non-Boolean domains
- The complexity of satisfiability problems
- The complexity of solving equations over finite groups
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The hardness of 3-uniform hypergraph coloring
- The power of Sherali-Adams relaxations for general-valued CSPs
- The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
- The right adjoints into the categories of relational systems
- Topology and Adjunction in Promise Constraint Satisfaction
- Two-element structures modulo primitive positive constructability
Cited in
(7)- Quantum advantage and CSP complexity
- Approximate graph coloring and the crystal with a hollow shadow
- Semidefinite programming and linear equations vs. homomorphism problems
- Solving promise equations over monoids and groups
- The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
- Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
- Three fundamental questions in modern infinite-domain constraint satisfaction
This page was built for publication: Local consistency as a reduction between constraint satisfaction problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6970248)
