Publication at Faculty of Mathematics and Physics |
2012
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(ε) RIGHTWARDS ARROW 0 as ε RIGHTWARDS ARROW 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.