We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Robust satisfiability for CSPs : hardness and algorithmic results.

Dalmau, V. and Krokhin, A. (2013) 'Robust satisfiability for CSPs : hardness and algorithmic results.', ACM transactions on computation theory., 5 (4). p. 15.


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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:© ACM 2013. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on Computation Theory, 5, 4, 15, 2013,
Date accepted:No date available
Date deposited:06 June 2014
Date of first online publication:November 2013
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar