Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs
DOI10.1137/18M1163932zbMath1452.68087arXiv1607.04787WikidataQ114074308 ScholiaQ114074308MaRDI QIDQ5203794
Marcin Kozik, Jakub Opršal, Konstantin Makarychev, Victor Dalmau, Yury Makarychev, Andrei A. Krokhin
Publication date: 9 December 2019
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1607.04787
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- CSP duality and trees of bounded pathwidth
- Bounded width problems and algebras
- Universal algebra and hardness results for constraint satisfaction problems
- Constraint satisfaction from a deductive viewpoint
- Polynomial interpolation and the Chinese remainder theorem for algebraic systems
- Constraints, consistency and closure
- Characterising tractable constraints
- Characterizations of several Maltsev conditions.
- Majority constraints have bounded pathwidth duality
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- Robustly Solvable Constraint Satisfaction Problems
- Linear programming, width-1 CSPs, and robust satisfaction
- Near-optimal algorithms for unique games
- On the usefulness of predicates
- Robust Satisfiability for CSPs
- Near Unanimity Constraints Have Bounded Pathwidth Duality
- Two new homomorphism dualities and lattice operations
- Approximation Resistance from Pairwise-Independent Subgroups
- The Complexity of Finite-Valued CSPs
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- On the power of unique 2-prover 1-round games
- The structure of finite algebras
- 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
- Weak consistency notions for all the CSPs of bounded width
- Semidefinite Programming
- Finitely Related Algebras In Congruence Distributive Varieties Have Near Unanimity Terms
- Approximation Algorithms for CSPs
- The Power of Linear Programming for General-Valued CSPs
- A characterization of strong approximation resistance
- The Complexity of General-Valued CSPs
- Linear Datalog and Bounded Path Duality of Relational Structures
- Classifying the Complexity of Constraints Using Finite Algebras
- Towards a Characterization of Constant-Factor Approximable Min CSPs
- The complexity of satisfiability problems
- On the NP-Hardness of Max-Not-2
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Dualities for Constraint Satisfaction Problems
This page was built for publication: Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs
