Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs
En palabras de los autores
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 -accurate oracle: for each variable, the oracle outputs a label in that agrees with a fixed optimal assignment with probability , 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 -approximation using words of space in insertion-only streams, and words of space in dynamic streams. We substantially generalize and strengthen their result, provided that a highly accurate estimate of is available. For any Boolean Max-CSP and any independent of , we obtain, with high constant probability, a single-pass -approximation using words of space in insertion-only streams, and words of space in dynamic streams, where is the number of variables. We further extend our techniques to general Boolean Max-CSPs for , with slightly worse space complexity.
Apareció: jueves, 15 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: NeurIPS 2026