Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-163 | 2nd December 2011 21:08

Robust Satisfiability of Constraint Satisfaction Problems

RSS-Feed




TR11-163
Authors: Libor Barto, Marcin Kozik
Publication: 8th December 2011 15:48
Downloads: 3514
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint