Robustly Solvable Constraint Satisfaction Problems

Abstract

An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least $(1-g(\epsilon ))$-fraction of the constraints given a $(1-\epsilon )$-satisfiable instance, where $g(\epsilon )\to 0$ as $\epsilon \to 0$. Guruswami and Zhou conjectured a characterization of constraint languages for which the corresponding constraint satisfaction problem admits an efficient robust algorithm. This paper confirms their conjecture.