DIMACS Theoretical Computer Science Seminar

Title: Superlinear lower bounds for multipass graph processing

Speaker: Krysztof Onak, Thomas J. Watson Research Center

Date: Wednesday, February 6, 2013 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

I will present n^(1+Omega(1/p)) lower bounds for the space complexity of p-pass streaming algorithms for the following problems on n-vertex graphs:

computing maximum matching size,
testing if two specific vertices are at distance at most 2(p+1),
testing if there is a directed path between two specific vertices.

Before our result, it was known that these problems require Omega(n^2) space in one pass, but no n^(1+Omega(1)) lower bound was known for any p >= 2.

Our result follows 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 reachable from a specific vertex in exactly p+1 steps intersect. The game requires a significant amount of communication only if the players are forced to speak in a specific difficult order.

Joint work with Venkat Guruswami.

See: http://paul.rutgers.edu/~yixinxu/theory-spring13.html