We prove first n^(1+\Omega(1)) lower bounds for the space complexity of multipass streaming algorithms for problems such as maximum matching, shortest path, and directed connectivity. More precisely, if the number of passes is a constant p, we show that these problems require n^(1+\Omega(1/p)) space. Prior to our result, it was known that they need Omega(n^2) space in one pass, but no n^(1+\Omega(1)) lower bound was known for any p >= 2.

Our results follow from a communication complexity lower bound for a communication game in which the players hold two graphs on the same set of vertices. The task of the players is to find out whether the sets of vertices at distance exactly p+1 from a specific vertex intersect. The game requires a significant amount of communication only if the players are forced to speak in a specific difficult order. This is reminiscent of lower bounds for communication problems such as indexing and pointer chasing. Among other things, our line of attack requires proving an information cost lower bound for a decision version of the classic pointer chasing problem and a direct sum type theorem for the disjunction of several instances of this problem.

Joint work with Venkatesan Guruswami.