2026-07-23T00:26:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22672 2026-04-17T05:32:07Z ddc:004 open_access

Learning-Augmented Streaming Algorithms for Approximating MAX-CUT Dong, Yinhao Peng, Pan Vakilian, Ali Learning-Augmented Algorithms Graph Streaming Algorithms MAX-CUT 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 ε > 0, any (randomized) single-pass streaming algorithm that achieves an approximation ratio of at least 1/2 + ε requires Ω(n / 2^poly(1/ε)) 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 ε-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 + ε, 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 + Ω(ε²) with probability at least 2/3 for insertion-only streams, using only poly(1/ε) words of space. We also extend our algorithm to fully dynamic streams while maintaining a space complexity of poly(1/ε,log n) words. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yinhao Dong and Pan Peng and Ali Vakilian 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.44 urn:nbn:de:0030-drops-226728 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.44 eng https://creativecommons.org/licenses/by/4.0/legalcode