Polynomial Pass Lower Bounds for Graph Streaming Algorithms

Sepehr Assadi, Yu Chen, Sanjeev Khanna

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 instan…