Robust satisfiability for CSPs : hardness and algorithmic results.

Abstract

An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least a (1 − f(ε))-fraction of constraints for each (1 − ε)-satisfiable instance (i.e., such that at most a ε-fraction of constraints needs to be removed to make the instance satisfiable), where f(ε) → 0 as ε → 0. We establish an algebraic framework for analyzing constraint satisfaction problems admitting an efficient robust algorithm with functions f of a given growth rate. We use this framework to derive hardness results. We also describe three classes of problems admitting an efficient robust algorithm such that f is O(1/log (1/ε)), O(ε1/k) for some k > 1, and O(ε), respectively. Finally, we give a complete classification of robust satisfiability with a given f for the Boolean case.