SDPs and robust satisfiability of promise CSP
From MaRDI portal
Publication:6499252
DOI10.1145/3564246.3585180MaRDI QIDQ6499252FDOQ6499252
Authors: Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
Publication date: 8 May 2024
approximation algorithmsSemidefinite programmingpromise constraint satisfaction problemssphere Ramsey theory
Cites Work
- Closure properties of constraints
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- Some optimal inapproximability results
- On the algebraic structure of combinatorial problems
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Title not available (Why is that?)
- Title not available (Why is that?)
- Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set
- Title not available (Why is that?)
- On Ramsey sets in spheres
- CSP gaps and reductions in the lasserre hierarchy
- On the integrality ratio of semidefinite relaxations of MAX CUT
- Near-optimal algorithms for maximum constraint satisfaction problems
- The power of Sherali-Adams relaxations for general-valued CSPs
- Title not available (Why is that?)
- Robustly solvable constraint satisfaction problems
- Absorption in universal algebra and CSP
- \((2+\varepsilon)\)-Sat is NP-hard
- A proof of the CSP dichotomy conjecture
- Algebraic Approach to Promise Constraint Satisfaction
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
- Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
- An algorithmic blend of LPs and ring equations for promise CSPs
- Title not available (Why is that?)
- The complexity of promise SAT on non-Boolean domains
- Improved Inapproximability of Rainbow Coloring
- The limits of SDP relaxations for general-valued CSPs
- Title not available (Why is that?)
- CLAP: A New Algorithm for Promise CSPs
- Title not available (Why is that?)
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)