Certifiable near-optimal solutions unify search and refutation in random csp problems
Certifiable Near-Optimality: A Simple Framework for Unifying Search and Refutation for (Semi)random CSPs
Data Structures and Algorithms
Summary
Constraint satisfaction problems (CSPs) involve finding solutions that satisfy many rules or constraints. The paper studies two types of random CSPs: ones that are usually unsolvable and ones designed to have a hidden solution. The authors show that known algorithms for these problems actually produce solutions with a certificate proving the solution is nearly the best possible. They also design new algorithms that handle cases where some constraints have been tampered with, still ensuring nearly optimal and verifiable solutions.
What this means in practice
- •For constraint solver developers: Create CSP solvers that guarantee near-optimal solutions with certificates even when some problem constraints are adversarially corrupted.
- •For complexity theory tool builders: Develop frameworks connecting search and refutation tasks under random and semirandom CSP models using certifiable optimality guarantees.
Authors
Prashanti Anderson, Peter Manohar, Jeff Xu
Abstract
A classical problem in average-case complexity is the study of random constraint satisfaction problems (CSPs). Random CSPs are traditionally studied in two different settings: refutation, where the instances are uniformly random and thus unsatisfiable with high probability, and search, where the instances are drawn from a planted model so that they are satisfiable. While there is no formal relationship between the refutation and search variants of random CSPs, known algorithms are strikingly similar with near-identical computational thresholds. In this work, we establish a formal relationship between the known algorithms for refutation and search by showing that in either case they achieve a stronger guarantee: they output an assignment $x$ along with a certificate $π$ that the fraction of constraints satisfied by $x$ is within some small $\varepsilon$ of the optimal assignment. We call this guarantee certifiable $\varepsilon$-optimality. As an application, we design new algorithms for a model of semirandom CSPs where the instance hypergraph (or scopes) is random, but the literal negation patterns are adversarially chosen and may depend on the hypergraph. For such CSPs, we give a family of algorithms that output certifiably $\varepsilon$-optimal solutions. We additionally study such semirandom CSPs in the "strong contamination model", where an adversary is allowed to corrupt an $O(δ)$-fraction of constraints after seeing the initial CSP. For such CSPs, we give an algorithm to output a certifiably $O(δ)$-optimal solution.