Polynomial pass lower bounds for graph streaming algorithms
Sepehr Assadi, Yu Chen, Sanjeev Khanna · 2019
We present new lower bounds that show that a polynomial number of passes are necessary for solving some fundamental graph problems in the streaming model of computation. For instance, we show that any streaming algorithm that finds a weighted minimum s-t cut in an n-vertex undirected graph requires n2−o(1) space unless it makes nΩ(1) passes over the stream.