Conference
Aug 2026
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...
S. S, Matan P, Krithikha Sanju S et al.
· International Conference Com... · 0 citations