Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs

We study learning-augmented streaming algorithms for estimating the value of Boolean Maximum Constraint Satisfaction Problems (Max-CSPs). Specifically, we consider streaming algorithms equipped with an $\epsilon$-accurate oracle: for each variable, the oracle outputs a label in $-1,1$ that agrees with a fixed optimal assignment with probability $1/2+\epsilon$, and disagrees otherwise. Prior work by Dong, Peng, and Vakilian [2025] showed that, for the special case of Max-Cut, such an oracle enables a $(1/2+\Omega ({\epsilon }^2))$-approximation using $\mathrm{poly}(1/\epsilon )$ words of space in insertion-only streams, and $\mathrm{poly}(1/\epsilon ,\log n)$ words of space in dynamic streams. We substantially generalize and strengthen their result, provided that a highly accurate estimate of $\epsilon$ is available. For any Boolean Max-$2$CSP and any $\eta >0$ independent of $\epsilon$, we obtain, with high constant probability, a single-pass $(1-\eta )$-approximation using $\mathrm{poly}(1/\epsilon ,1/\eta )$ words of space in insertion-only streams, and $\mathrm{poly}(1/\epsilon ,1/\eta ,\log n)$ words of space in dynamic streams, where $n$ is the number of variables. We further extend our techniques to general Boolean Max-$k$CSPs for $k\ge 3$, with slightly worse space complexity.