Robustly solvable constraint satisfaction problems

DOI10.1137/130915479MaRDI QIDQ2817797zbMATH OpenOpenAlexFDO

Authors Libor Barto, Marcin Kozik

Publication date 2 September 2016

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.01157

zbMATH Keywords

approximationbounded widthconstraint satisfaction problemrobust satisfiabilityuniversal algebra

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least $(1-g(varepsilon))$-fraction of the constraints given a $(1-varepsilon)$-satisfiable instance, where $g(varepsilon)ightarrow0$ as $varepsilonightarrow0$. Guruswami and Zhou conjectured a characterization of constraint languages for which the corresponding constraint satisfaction problem admits an efficient robust algorithm. This paper confirms their conjecture.

Recommendations

• Robust satisfiability of constraint satisfaction problems
• Robust satisfiability for CSPs: hardness and algorithmic results
• Linear programming, width-1 CSPs, and robust satisfaction
• Robust algorithms with polynomial loss for near-unanimity CSPs
• Robust algorithms with polynomial loss for near-unanimity CSPs

Cites work

• Bounded width problems and algebras
• Classifying the Complexity of Constraints Using Finite Algebras
• Closed systems of functions and predicates
• Closure properties of constraints
• Constraint Satisfaction Problems of Bounded Width
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Dualities for Constraint Satisfaction Problems
• Explicit dimension reduction and its applications
• Hard constraint satisfaction problems have hard gaps at location 1
• scientific article; zbMATH DE number 1670830 (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 6783493 (Why is no real title available?)
• scientific article; zbMATH DE number 3336786 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Linear programming, width-1 CSPs, and robust satisfaction
• Near-optimal algorithms for maximum constraint satisfaction problems
• Near-optimal algorithms for unique games
• On the power of unique 2-prover 1-round games
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Robust satisfiability for CSPs: hardness and algorithmic results
• Semidefinite Programming
• Some optimal inapproximability results
• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
• The approximability of constraint satisfaction problems
• The collapse of the bounded width hierarchy
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Universal algebra and hardness results for constraint satisfaction problems

Cited in

(27)

• Towards a characterization of constant-factor approximable finite-valued CSPs
• On a stronger reconstruction notion for monoids and clones
• The number of clones determined by disjunctions of unary relations
• Robust algorithms for restricted domains
• Linear programming, width-1 CSPs, and robust satisfaction
• Robust satisfiability for CSPs: hardness and algorithmic results
• Robust algorithms with polynomial loss for near-unanimity CSPs
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Solving CSPs using weak local consistency
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• Robust algorithms with polynomial loss for near-unanimity CSPs
• The complexity of general-valued CSPs
• The power of Sherali-Adams relaxations for general-valued CSPs
• Binarisation for valued constraint satisfaction problems
• Robust satisfiability of constraint satisfaction problems
• CLAP: A New Algorithm for Promise CSPs
• Topology and Adjunction in Promise Constraint Satisfaction
• SDPs and robust satisfiability of promise CSP
• Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
• Quantum advantage and CSP complexity
• 1-in-3 vs. not-all-equal: dichotomy of a broken promise
• Quantum advantage and CSP complexity
• Algebraic approach to approximation
• Semidefinite programming and linear equations vs. homomorphism problems
• 1-in-3 vs. not-all-equal: dichotomy of a broken promise
• Symmetries and complexity (invited talk)
• Satisfiability of commutative vs. non-commutative CSPs

This page was built for publication: Robustly solvable constraint satisfaction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817797)