ECCC-Report TR11-163https://eccc.weizmann.ac.il/report/2011/163Comments and Revisions published for TR11-163en-usThu, 08 Dec 2011 15:48:17 +0200
Paper TR11-163
| Robust Satisfiability of Constraint Satisfaction Problems |
Libor Barto,
Marcin Kozik
https://eccc.weizmann.ac.il/report/2011/163An 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.
Thu, 08 Dec 2011 15:48:17 +0200https://eccc.weizmann.ac.il/report/2011/163