CLAP: A New Algorithm for Promise CSPs

DOI10.1137/22M1476435MaRDI QIDQ5885595zbMATH OpenOpenAlexFDO

Authors Lorenzo Ciardo, S. Zivny

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

homomorphism problemslinear programmingpromise 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)

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)