All reports by Author Marcin Kozik:

__
TR11-163
| 2nd December 2011
__

Libor Barto, Marcin Kozik#### Robust Satisfiability of Constraint Satisfaction Problems

Libor Barto, Marcin Kozik

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 ...
more >>>