Robust Satisfiability for CSPs: Hardness and Algorithmic Results

Dalmau, V.; Krokhin, A.

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
• Electronic ISSN: 1942-3462
• Publisher: Association for Computing Machinery (ACM)
• Peer Reviewed: Peer Reviewed
• Volume: 5
• Issue: 4
• Article Number: 15
• DOI: https://doi.org/10.1145/2540090
• Public URL: https://durham-repository.worktribe.com/output/1427938