ECCC-Report TR13-002https://eccc.weizmann.ac.il/report/2013/002Comments and Revisions published for TR13-002en-usMon, 08 Feb 2016 23:14:25 +0200
Revision 3
| Superlinear lower bounds for multipass graph processing |
Venkatesan Guruswami,
Krzysztof Onak
https://eccc.weizmann.ac.il/report/2013/002#revision3We prove $n^{1+\Omega(1/p)}/p^{O(1)}$ lower bounds for the space complexity of $p$-pass streaming algorithms solving the following problems on $n$-vertex graphs:
* testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size),
* testing if two specific vertices are at distance at most $2(p+1)$ in an undirected graph,
* testing if there is a directed path from $s$ to $t$ for two specific vertices $s$ and $t$ in a directed graph.
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\ge 2$.
These streaming 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 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. 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.
Mon, 08 Feb 2016 23:14:25 +0200https://eccc.weizmann.ac.il/report/2013/002#revision3
Revision 2
| Superlinear lower bounds for multipass graph processing |
Venkatesan Guruswami,
Krzysztof Onak
https://eccc.weizmann.ac.il/report/2013/002#revision2We prove $n^{1+\Omega(1/p)}/p^{O(1)}$ lower bounds for the space complexity of $p$-pass streaming algorithms solving the following problems on $n$-vertex graphs:
* testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size),
* testing if two specific vertices are at distance at most $2(p+1)$ in an undirected graph,
* testing if there is a directed path from $s$ to $t$ for two specific vertices $s$ and $t$ in a directed graph.
Prior to 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\ge 2$.
These streaming 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.
Mon, 18 Aug 2014 19:00:37 +0300https://eccc.weizmann.ac.il/report/2013/002#revision2
Revision 1
| Superlinear lower bounds for multipass graph processing |
Venkatesan Guruswami,
Krzysztof Onak
https://eccc.weizmann.ac.il/report/2013/002#revision1We prove $n^{1+\Omega(1/p)}/p^{O(1)}$ lower bounds for the space complexity of $p$-pass streaming algorithms solving the following problems on $n$-vertex graphs:
* testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size),
* testing if two specific vertices are at distance at most $2(p+1)$ in an undirected graph,
* testing if there is a directed path from $s$ to $t$ for two specific vertices $s$ and $t$ in a directed graph.
Prior to 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\ge 2$.
These streaming 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 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. 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.
Wed, 20 Mar 2013 03:50:35 +0200https://eccc.weizmann.ac.il/report/2013/002#revision1
Paper TR13-002
| Superlinear lower bounds for multipass graph processing |
Venkatesan Guruswami,
Krzysztof Onak
https://eccc.weizmann.ac.il/report/2013/002We prove $n^{1+\Omega(1/p)}/p^{O(1)}$ lower bounds for the space complexity of $p$-pass streaming algorithms solving the following problems on $n$-vertex graphs:
* testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size),
* testing if two specific vertices are at distance at most $2(p+1)$ in an undirected graph,
* testing if there is a directed path from $s$ to $t$ for two specific vertices $s$ and $t$ in a directed graph.
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\ge 2$.
These streaming 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 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. 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.
Wed, 02 Jan 2013 16:14:30 +0200https://eccc.weizmann.ac.il/report/2013/002