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 n 2− o (1) space unless it makes n Ω(1) passes over the stream.

Authors

• Sepehr Assadi
• Yu Chen 0039
• Sanjeev Khanna

Keywords

• Communication complexity
• Graph streaming
• Lower bounds