Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR11-163 | 2nd December 2011 21:08

#### Robust Satisfiability of Constraint Satisfaction Problems

TR11-163
Authors: Libor Barto, Marcin Kozik
Publication: 8th December 2011 15:48
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$.