7 papers
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},\,…
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…
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…
MAX BISECTION might be harder to approximate than MAX CUT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
The MAX BISECTION problem seeks a maximum-size cut that evenly divides the vertices of a given undirected graph. An open problem raised by Austrin, Benabbas, and Georgiou is whethe…
Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
Neng Huang, Will Perkins, Aaron Potechin
We prove a hardness of sampling result for the anti-ferromagnetic Ising model on random graphs of average degree for large constant , proving that when the normalized invers…
Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
Pravesh Kothari, Aaron Potechin, Jeff Xu
We prove that for every , and large enough constant , with high probability over the choice of , the \Erdos-\Renyi random graph distribution, t…
Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
Susanna F. de Rezende, Aaron Potechin, Kilian Risse
We prove that Sherali-Adams with polynomially bounded coefficients requires proofs of size to rule out the existence of an -clique in Erdős-Rényi random graphs…