5 citations · 6 across the 8 of their papers we have counts for
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…
math.PR2026
Sharp Phase Transition for Ellipsoid Fitting
Sofia de la Cerda, Aaron Potechin, Madhur Tulsiani +1
We resolve the ellipsoid fitting conjecture of Saunderson, Chandrasekaran, Parrilo, and Willsky up to a vanishing factor. Concretely, for independent Gaussian points in dimensi…