TagsArticle Source
Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability
Abstract
We prove that any o($\sqrt{\log n}$)-pass streaming algorithm requires n2−o(1) space to solve the Reachability problem for directed graphs (given two vertices s and t, determine whether s can reach t in the given graph). By known reductions, our result implies the same almost quadratic lower bounds for other problems, including maximum matching, shortest path, matrix rank, and linear programming.
The construction of our hard instances makes crucial use of Ruzsa-Szemeŕedi graphs and low-depth sorting networks.