Robust algorithms with polynomial loss for near-unanimity CSPs

Dalmau, Víctor; Kozik, Marcin; Krokhin, Andrei; Makarychev, Konstantin; Makarychev, Yury; Opršal, Jakub

doi:http://dx.doi.org/10.1137/18M1163932

Robust algorithms with polynomial loss for near-unanimity CSPs

License

Citation

Dalmau V, Kozik M, Krokhin A, Makarychev K, Makarychev Y, Opršal J. Robust algorithms with polynomial loss for near-unanimity CSPs. SIAM J Sci Comput. 2019 Nov 26;48(6):1763-95. DOI: 10.1137/18M1163932

Abstract

An instance of the constraint satisfaction problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints. An approximation algorithm for a CSP is called robust if it outputs an assignment satisfying an (1 - g(ϵ))-fraction of constraints on any (1 ϵ)- satisfiable instance, where the loss function g is such that g(ϵ) → 0 as ϵ → 0. We study how the robust approximability of CSPs depends on the set of constraint relations allowed in instances, the so-called constraint language. All constraint languages admitting a robust polynomial-time algorithm (with some g) have been characterized by Barto and Kozik, with the general bound on the loss g being doubly exponential, specifically g(ϵ) = O((log log(1/ϵ))/ log(1/ϵ)). It is natural to ask when a better loss can be achieved, in particular polynomial loss g(ϵ) = O(ϵ1/k) for some constant k. In this paper, we consider CSPs with a constraint language having a near-unanimity polymorphism. This general condition almost matches a known necessary condition for having a robust algorithm with polynomial loss. We give two randomized robust algorithms with polynomial loss for such CSPs: one works for any near-unanimity polymorphism and the parameter k in the loss depends on the size of the domain and the arity of the relations in Γ, while the other works for a special ternary near-unanimity operation called the dual discriminator with k = 2 for any domain size. In the latter case, the CSP is a common generalization of Unique Games with a fixed domain and 2-Sat. In the former case, we use the algebraic approach to the CSP. Both cases use the standard semidefinite programming relaxation for the CSP.