Learning-augmented streaming improves max-csp approximations with less memory
Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs
Data Structures and Algorithms
Summary
This paper looks at ways to better estimate solutions to complex logic puzzles called Boolean Max-CSPs using streaming algorithms — methods that process data in a single pass using limited memory. The authors use a helpful oracle that guesses each variable's value slightly better than random chance. Building on earlier work that focused on a simpler problem called Max-Cut, they extend their approach to a wider range of puzzles and improve the quality of approximations while still using little memory. Their techniques work in different data streaming models and for more complex puzzles with many variables.
What this means in practice
- •For data engineers: Improve memory-efficient estimation of complex constraint satisfaction problems in large streaming datasets using learning-augmented algorithms.
- •For algorithm developers: Design more accurate one-pass algorithms for constraint optimization tasks with limited memory by incorporating mildly accurate predictions.
Authors
Yinhao Dong, Pan Peng, Ali Vakilian, Santhoshini Velusamy, Xiaoyang Xu
Abstract
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 $\varepsilon$-accurate oracle: for each variable, the oracle outputs a label in $\{-1,1\}$ that agrees with a fixed optimal assignment with probability $1/2+\varepsilon$, and disagrees otherwise. Prior work by Dong, Peng, and Vakilian [ITCS 2025] showed that, for the special case of Max-Cut, such an oracle enables a $(1/2+Ω(\varepsilon^2))$-approximation using $\operatorname{poly}(1/\varepsilon)$ words of space in insertion-only streams, and $\operatorname{poly}(1/\varepsilon,\log n)$ words of space in dynamic streams. We substantially generalize and strengthen their result, provided that a highly accurate estimate of $\varepsilon$ is available. For any Boolean Max-$2$CSP and any $η>0$ independent of $\varepsilon$, we obtain, with high constant probability, a single-pass $(1-η)$-approximation using $\operatorname{poly}(1/\varepsilon,1/η)$ words of space in insertion-only streams, and $\operatorname{poly}(1/\varepsilon,1/η,\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.