2026-09-08T01:21:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26529 2026-09-05T19:46:35Z ddc:004 open_access

Streaming Complexity Separations for Dense and Sparse Graphs Liu, Yang P. Nguyen, Hoai-An Singer, Noah G. Woodruff, David P. streaming maximum cut complexity separations We identify a sharp separation in the streaming space complexity of Maximum Cut when the algorithm must output an approximate cut (rather than only the approximate value). For dense graphs, we show that O(n/ε²) space is sufficient and that Ω(n) space is necessary. In contrast, for graphs with Θ(n/ε²) edges, the situation is markedly different: we show that the problem requires Ω(n log(ε² n)/ε²) space for any ε = ω(1/√n), which is tight for the full range of ε. We also give an Ω(n log n/ε²)-space lower bound against deterministic algorithms for outputting a (1-ε) approximation to the value of the maximum cut. Using similar techniques we prove an analogous sharp separation in the streaming space complexity of Densest Subgraph and show that for every constant-arity CSP over a constant-size alphabet and the Similarity problem the space complexity in dense streams can be improved by shaving a logarithmic factor. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yang P. Liu and Hoai-An Nguyen and Noah G. Singer and David P. Woodruff 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.140 urn:nbn:de:0030-drops-265290 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.140 eng https://creativecommons.org/licenses/by/4.0/legalcode