SDPs and robust satisfiability of promise CSP
From MaRDI portal
Publication:6499252
Cites work
- scientific article; zbMATH DE number 5485464 (Why is no real title available?)
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 1775443 (Why is no real title available?)
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- scientific article; zbMATH DE number 7561550 (Why is no real title available?)
- scientific article; zbMATH DE number 7724184 (Why is no real title available?)
- scientific article; zbMATH DE number 7716602 (Why is no real title available?)
- A proof of the CSP dichotomy conjecture
- Absorption in universal algebra and CSP
- Algebraic Approach to Promise Constraint Satisfaction
- An algorithmic blend of LPs and ring equations for promise CSPs
- CLAP: A New Algorithm for Promise CSPs
- CSP gaps and reductions in the lasserre hierarchy
- Classifying the Complexity of Constraints Using Finite Algebras
- Closure properties of constraints
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Improved Inapproximability of Rainbow Coloring
- Near-optimal algorithms for maximum constraint satisfaction problems
- On Ramsey sets in spheres
- On the algebraic structure of combinatorial problems
- On the integrality ratio of semidefinite relaxations of MAX CUT
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Robustly solvable constraint satisfaction problems
- Some optimal inapproximability results
- Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
- The complexity of promise SAT on non-Boolean domains
- The complexity of satisfiability problems
- The limits of SDP relaxations 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
- Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set
- \((2+\varepsilon)\)-Sat is NP-hard
This page was built for publication: SDPs and robust satisfiability of promise CSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499252)