Showing cs.CCShow 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},\,…
cs.CC2025
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…
cs.CC2024
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…