期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We give an almost quadratic n2−o(1) lower bound on the space consumption of any o(logn) -pass streaming algorithm solving the (directed) s-t reachability problem. This means that any such algorithm must essentially store the entire graph. As corollaries, we obtain almost quadratic space lower bounds for additional fundamental problems, including maximum matching, shortest path, matrix rank, and linear programming. Our main technical contribution is the definition and construction of set hiding graphs, that may be of independent interest: we give a general way of encoding a set S[k] as a directed graph with n=k1+o(1) vertices, such that deciding whether iS boils down to deciding if ti is reachable from si, for a specific pair of vertices (siti) in the graph. Furthermore, we prove that our graph ``hides'' S, in the sense that no low-space streaming algorithm with a small number of passes can learn (almost) anything about S.
