Showing 2026Show all
2 papers · 1 filter
cs.DS2026
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…
cs.DS2026
A Simple Algorithm for Best Separable State
Prashanti Anderson, Samuel B. Hopkins, Amit Rajaraman
We study the best separable state problem (BSS), which asks for the maximum acceptance probability of a quantum measurement over unentangled states. In classical terms, the goal is…