Preprint
Sep 2026
Certifiable Near-Optimality: A Simple Framework for Unifying Search and Refutation for (Semi)random CSPs
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 fro...
Prashanti Anderson, Peter Manohar, Jeff Xu
· 0 citations