Certifiable Near-Optimality: A Simple Framework for Unifying Search and Refutation for (Semi)random CSPs

Prashanti Anderson, Peter Manohar, Jeff Xu

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: refu…