CLAP: A New Algorithm for Promise CSPs

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

zbMATH Keywords

linear programminghomomorphism problemspromise constraint satisfaction

Mathematics Subject Classification ID

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