Robust Satisfiability for CSPs: Hardness and Algorithmic Results

Dalmau, V.; Krokhin, A.

doi:10.1145/2540090

Robust Satisfiability for CSPs: Hardness and Algorithmic Results

Dalmau, V.; Krokhin, A.

Authors

V. Dalmau

Professor Andrei Krokhin andrei.krokhin@durham.ac.uk
Professor

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.

Citation

Dalmau, V., & Krokhin, A. (2013). Robust Satisfiability for CSPs: Hardness and Algorithmic Results. ACM Transactions on Computation Theory, 5(4), Article 15. https://doi.org/10.1145/2540090

Journal Article Type	Article
Publication Date	Nov 1, 2013
Deposit Date	May 29, 2014
Publicly Available Date	Jun 6, 2014
Journal	ACM Transactions on Computation Theory
Print ISSN	1942-3454
Publisher	Association for Computing Machinery (ACM)
Peer Reviewed	Peer Reviewed
Volume	5
Issue	4
Article Number	15
DOI	https://doi.org/10.1145/2540090

Files

Accepted Journal Article (202 Kb)
PDF

Copyright 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, http://dx.doi.org/10.1145/2540090.