CLAP: A New Algorithm for Promise CSPs
From MaRDI portal
Publication:5885595
DOI10.1137/22M1476435OpenAlexW3177905337MaRDI QIDQ5885595
Lorenzo Ciardo, Stanislav Živný
Publication date: 4 April 2023
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2107.05018
Analysis of algorithms and problem complexity (68Q25) General topics of discrete mathematics in relation to computer science (68R01) Linear programming (90C05)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new line of attack on the dichotomy conjecture
- There are no pure relational width 2 constraint satisfaction problems
- On the complexity of H-coloring
- Consistency in networks of relations
- On the algebraic structure of combinatorial problems
- The wonderland of reflections
- Tractable decision for a constraint language implies tractable search
- Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
- The hardness of 3-uniform hypergraph coloring
- Theoretical analysis of singleton arc consistency and its extensions
- Robustly Solvable Constraint Satisfaction Problems
- The collapse of the bounded width hierarchy
- Linear programming, width-1 CSPs, and robust satisfaction
- Robust Satisfiability for CSPs
- Logical compactness and constraint satisfaction problems
- Proof verification and the hardness of approximation problems
- The Complexity of Finite-Valued CSPs
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Algebraic Properties of Valued Constraint Satisfaction Problem
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- Varieties with few subalgebras of powers
- On the power of unique 2-prover 1-round games
- Improving the performance guarantee for approximate graph coloring
- Probabilistic checking of proofs
- The Complexity of Near-Optimal Graph Coloring
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- New approximation algorithms for graph coloring
- Closure properties of constraints
- Discrete Temporal Constraint Satisfaction Problems
- On the Hardness of 4-Coloring a 3-Colorable Graph
- Arc consistency and friends
- The Limits of SDP Relaxations for General-Valued CSPs
- Solving CSPs Using Weak Local Consistency
- Algebraic Approach to Promise Constraint Satisfaction
- The Complexity of Promise SAT on Non-Boolean Domains
- Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy
- A Proof of the CSP Dichotomy Conjecture
- The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems
- 𝜔-categorical structures avoiding height 1 identities
- Improved hardness for H-colourings of G-colourable graphs
- Improved Inapproximability of Rainbow Coloring
- Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs
- Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
- An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
- The Power of Linear Programming for General-Valued CSPs
- The Complexity of General-Valued CSPs
- Classifying the Complexity of Constraints Using Finite Algebras
- The Power of Sherali--Adams Relaxations for General-Valued CSPs
- $(2+\varepsilon)$-Sat Is NP-hard
- Tractability and Learnability Arising from Algebras with Few Subpowers
- The complexity of satisfiability problems
- A Simple Algorithm for Mal'tsev Constraints
- The PCP theorem by gap amplification
- On the hardness of approximating the chromatic number
This page was built for publication: CLAP: A New Algorithm for Promise CSPs