Polynomial pass lower bounds for graph streaming algorithms
Polynomial pass lower bounds for graph streaming algorithms
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 …