2026-07-22T13:15:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25342 2026-03-19T13:03:46Z ddc:004 open_access

Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs Efremenko, Klim Kol, Gillat Saxena, Raghuvansh R. Zhang, Zhijun Random Walk streaming Algorithm universal Optimality Sampling a random walk is a fundamental primitive in many graph applications. In the streaming model, it is known that sampling an L-step random walk on an n-vertex directed graph requires Ω(n L) space, implying that no sublinear-space streaming algorithm exists for general graphs. We show that sublinear algorithms are possible for the case of dense graphs, where every vertex has out-degree at least Ω(n). In particular, we give a one-pass turnstile streaming algorithm that uses only 𝒪̃(L) memory for such graphs. More broadly, for graphs with minimum out-degree at least d, our streaming algorithm samples a random walk using 𝒪̃(n/d ⋅ L) memory. We show that our algorithm is optimal in a strong "beyond worst-case" sense. To formalize this, we introduce the notion of universal optimality for graph streaming algorithms. Informally, a streaming algorithm is universally optimal if it performs (almost) as well as possible on every graph, assuming a worst-case choice of the streaming order. This notion of universal optimality is a key conceptual contribution of our work. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Klim Efremenko and Gillat Kol and Raghuvansh R. Saxena and Zhijun Zhang 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.55 urn:nbn:de:0030-drops-253423 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.55 eng https://creativecommons.org/licenses/by/4.0/legalcode