Recommendations
- CLAP: a new algorithm for promise CSPs
- An algorithmic blend of LPs and ring equations for promise CSPs
- The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
- Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
- Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
Cites work
- \( \omega \)-categorical structures avoiding height 1 identities
- (2+)-Sat is NP-hard
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- A new line of attack on the dichotomy conjecture
- A proof of the CSP dichotomy conjecture
- A Simple Algorithm for Mal'tsev Constraints
- Algebraic Approach to Promise Constraint Satisfaction
- Algebraic properties of valued constraint satisfaction problem
- An algorithmic blend of LPs and ring equations for promise CSPs
- Arc consistency and friends
- Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
- Classifying the Complexity of Constraints Using Finite Algebras
- Closure properties of constraints
- Consistency in networks of relations
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Dichotomy for symmetric Boolean PCSPs
- Discrete temporal constraint satisfaction problems
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 1487982 (Why is no real title available?)
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Improved hardness for \(H\)-colourings of \(G\)-colourable graphs
- Improved Inapproximability of Rainbow Coloring
- Improving the performance guarantee for approximate graph coloring
- Linear programming, width-1 CSPs, and robust satisfaction
- Logical compactness and constraint satisfaction problems
- New approximation algorithms for graph coloring
- On the algebraic structure of combinatorial problems
- On the complexity of H-coloring
- On the Hardness of 4-Coloring a 3-Colorable Graph
- On the hardness of approximating the chromatic number
- On the power of unique 2-prover 1-round games
- Probabilistic checking of proofs
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Proof verification and the hardness of approximation problems
- Robust algorithms with polynomial loss for near-unanimity CSPs
- Robust satisfiability for CSPs: hardness and algorithmic results
- Robustly solvable constraint satisfaction problems
- Solving CSPs using weak local consistency
- The collapse of the bounded width hierarchy
- The complexity of general-valued CSPs
- 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 hardness of 3-uniform hypergraph coloring
- The limits of SDP relaxations for general-valued CSPs
- The PCP theorem by gap amplification
- The power of linear programming for general-valued CSPs
- 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 wonderland of reflections
- Theoretical analysis of singleton arc consistency and its extensions
- There are no pure relational width 2 constraint satisfaction problems
- Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
- Tractability and learnability arising from algebras with few subpowers
- Tractable decision for a constraint language implies tractable search
- Varieties with few subalgebras of powers
Cited in
(15)- SDPs and robust satisfiability of promise CSP
- Approximate graph colouring and the hollow shadow
- CLAP: a new algorithm for promise CSPs
- Quantum advantage and CSP complexity
- Solving promise equations over monoids and groups
- Approximate graph coloring and the crystal with a hollow shadow
- 1-in-3 vs. not-all-equal: dichotomy of a broken promise
- Quantum advantage and CSP complexity
- Algebraic approach to approximation
- Injective hardness condition for PCSPs
- Semidefinite programming and linear equations vs. homomorphism problems
- 1-in-3 vs. not-all-equal: dichotomy of a broken promise
- On the complexity of symmetric vs. functional PCSPs
- Solving promise equations over monoids and groups
- On approximability of satisfiable k-CSPs: V
This page was built for publication: CLAP: A New Algorithm for Promise CSPs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5885595)
