Robust algorithms for near-unanimity CSPs

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. An algorithm for CSP is called robust if it outputs an almost satisfying assigment for every almost satisfiable instance - more precisely, an assignment satisfying a $(1-g(\eps))$-fraction of constraints on any $(1-\eps)$-satisfiable instance, where the loss function $g$ tends to 0 as  $\eps$ approaches 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 characterised by Barto and Kozik, with the general bound on the loss $g$ being doubly exponential. In this work, we give robust algorithms with polynomial loss for a family of CSPs satisfying a certain algebraic  condition, which almost matches a necessary algebraic condition for having such algorithms.

This is joint work with V.Dalmau, M.Kozik, K.Makarychev, Y.Makarychev, and J.Oprsal.