Robust satisfiability of constraint satisfaction problems

Abstract

An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least (1-g(ε))-fraction of the constraints given a (1-ε)-satisfiable instance, where g(ε) -> 0 as ε -> 0, $g(0)=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.