Abstrakt
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) -> 0 as epsilon -> 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.