Showing 2026Show all
3 papers · 1 filter
cs.CC2026
Sharp Lovasz-Theta Bounds on Random Graphs
Aaron Potechin, Jeff Xu
It is well known that the \Lovasz-Theta function of a random graph is . More precisely, it is tightly concentrated in the interval \( [\sqrt{n},\,…
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…
cs.DS2026
New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami +2
In this paper, we continue the study of robust satisfiability of promise CSPs (PCSPs), initiated in (Brakensiek, Guruswami, Sandeep, STOC 2023 / Discrete Analysis 2025), and obtain…