S. S. Geoffrey

Beyond Uniformity in Combinatorial Streams: Sparsity-Adaptive and Adversarially Robust Oracles for MAX-CUT Approximation

Recent advances in learning-augmented streaming show that access to an $\epsilon$-accurate oracle enables single-pass sublinear-space algorithms to surpass the classical 1/2 approximation barrier for MAX-CUT, achieving guarantees of $1 / 2+\Omega\left(\epsilon^{2}\right)$. However, existing formulations implicitly assu...