Learning-Augmented Streaming Algorithms for Approximating MAX-CUT

Abstract

We study learning-augmented streaming algorithms for estimating the value of MAX-CUT in a graph. In the classical streaming model, while a $1/2$-approximation for estimating the value of MAX-CUT can be trivially achieved with $O(1)$ words of space, Kapralov and Krachun [STOC'19] showed that this is essentially the best possible: for any $\hat{I}\mu >0$, any (randomized) single-pass streaming algorithm that achieves an approximation ratio of at least $1/2+\hat{I}\mu$ requires $\hat{I}\text{c◯}(n/2^{\text{poly}(1/\hat{I}\mu )})$ space. We show that it is possible to surpass the $1/2$-approximation barrier using just $O(1)$ words of space by leveraging a (machine learned) oracle. Specifically, we consider streaming algorithms that are equipped with an $\hat{I}\mu$-accurate oracle that for each vertex in the graph, returns its correct label in $\{-1,+1\}$, corresponding to an optimal MAX-CUT solution in the graph, with some probability $1/2+\hat{I}\mu$, and the incorrect label otherwise. Within this framework, we present a single-pass algorithm that approximates the value of MAX-CUT to within a factor of $1/2+\hat{I}\text{c◯}(\hat{I}{\mu }^2)$ with probability at least $2/3$ for insertion-only streams, using only $\text{poly}(1/\hat{I}\mu )$ words of space. We also extend our algorithm to fully dynamic streams while maintaining a space complexity of $\text{poly}(1/\hat{I}\mu ,\log n)$ words.

ITCS 2025