Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs
type: Item
instance of: scholarly article
title: Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs
zbMATH Open document ID: 1452.68087
DOI: 10.1137/18M1163932
author: Víctor Dalmau
author: Marcin Kozik
author: Andrei Krokhin
author: Konstantin Makarychev
author: Yury Makarychev
author: Jakub Opršal
published in: SIAM Journal on Computing
publication date: 2019-12-09T00:00:00Z
full work available at URL: https://arxiv.org/abs/1607.04787
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 7141256
zbMATH Keywords: constraint satisfaction
zbMATH Keywords: approximation algorithms
zbMATH Keywords: robust algorithm
zbMATH Keywords: near-unanimity polymorphism
Wikidata QID: Q114074308
MaRDI profile type: MaRDI publication profile
arXiv ID: 1607.04787
cites work: On the usefulness of predicates
cites work: Polynomial interpolation and the Chinese remainder theorem for algebraic systems
cites work: Finitely Related Algebras In Congruence Distributive Varieties Have Near Unanimity Terms
cites work: Constraint Satisfaction Problems Solvable by Local Consistency Methods
cites work: Robustly solvable constraint satisfaction problems
cites work: Near Unanimity Constraints Have Bounded Pathwidth Duality
cites work: Q4993594
cites work: Constraint satisfaction from a deductive viewpoint
cites work: Classifying the Complexity of Constraints Using Finite Algebras
cites work: Dualities for Constraint Satisfaction Problems
cites work: CSP duality and trees of bounded pathwidth
cites work: Two new homomorphism dualities and lattice operations
cites work: Approximation Resistance from Pairwise-Independent Subgroups
cites work: Near-optimal algorithms for unique games
cites work: Near-optimal algorithms for maximum constraint satisfaction problems
cites work: Characterising tractable constraints
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Linear Datalog and Bounded Path Duality of Relational Structures
cites work: Majority constraints have bounded pathwidth duality
cites work: Robust Satisfiability for CSPs
cites work: Towards a Characterization of Constant-Factor Approximable Min CSPs
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set
cites work: Some optimal inapproximability results
cites work: On the NP-Hardness of Max-Not-2
cites work: The structure of finite algebras
cites work: Constraints, consistency and closure
cites work: Closure properties of constraints
cites work: Q4643956
cites work: On the power of unique 2-prover 1-round games
cites work: Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
cites work: A characterization of strong approximation resistance
cites work: The Complexity of General-Valued CSPs
cites work: The Power of Linear Programming for General-Valued CSPs
cites work: Weak consistency notions for all the CSPs of bounded width
cites work: Characterizations of several Maltsev conditions.
cites work: Linear programming, width-1 CSPs, and robust satisfaction
cites work: Universal algebra and hardness results for constraint satisfaction problems
cites work: OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
cites work: Bounded width problems and algebras
cites work: Approximation Algorithms for CSPs
cites work: Q3549708
cites work: The complexity of satisfiability problems
cites work: The Complexity of Finite-Valued CSPs
cites work: Semidefinite Programming
cites work: Q4542575
description: scientific article; zbMATH DE number 7141256