Robustly Solvable Constraint Satisfaction Problems

DOI10.1137/130915479zbMath1350.68127arXiv1512.01157OpenAlexW2964303025MaRDI QIDQ2817797

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

approximationconstraint satisfaction problemuniversal algebrabounded widthrobust satisfiability

Mathematics Subject Classification ID

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

Related Items

On a stronger reconstruction notion for monoids and clones ⋮ CLAP: A New Algorithm for Promise CSPs ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ The Complexity of General-Valued CSPs ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Unnamed Item ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ Unnamed Item ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ The number of clones determined by disjunctions of unary relations ⋮ Solving CSPs Using Weak Local Consistency

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hard constraint satisfaction problems have hard gaps at location 1
• Bounded width problems and algebras
• Universal algebra and hardness results for constraint satisfaction problems
• Closed systems of functions and predicates
• The Approximability of Constraint Satisfaction Problems
• The collapse of the bounded width hierarchy
• Linear programming, width-1 CSPs, and robust satisfaction
• Explicit Dimension Reduction and Its Applications
• Near-optimal algorithms for unique games
• Robust Satisfiability for CSPs
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• On the power of unique 2-prover 1-round games
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Closure properties of constraints
• Semidefinite Programming
• Constraint Satisfaction Problems of Bounded Width
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
• Dualities for Constraint Satisfaction Problems

This page was built for publication: Robustly Solvable Constraint Satisfaction Problems