Open Problems:29 - Revision history

Krzysztof Onak at 21:14, 26 June 2013

2013-06-26T21:14:24Z

Krzysztof Onak: updated header

2013-03-07T01:50:53Z

updated header

Krzysztof Onak: Missing link and making the reference to Feigenbaum et al. more accurate.

2012-12-22T04:29:24Z

Missing link and making the reference to Feigenbaum et al. more accurate.

Krzysztof Onak at 05:24, 16 November 2012

2012-11-16T05:24:27Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:51Z

1 revision

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 29: Strong Lower Bounds for Graph Problems}} {{Infobox |label1 = Proposed by |data1 = Krzysztof Onak |label2 = Source |data2 = [[Workshops:Kanpur_2009|K..."

2012-10-20T19:33:14Z

Created page with "{{DISPLAYTITLE:Problem 29: Strong Lower Bounds for Graph Problems}} {{Infobox |label1 = Proposed by |data1 = Krzysztof Onak |label2 = Source |data2 = [[Workshops:Kanpur_2009|K..."

New page

{{DISPLAYTITLE:Problem 29: Strong Lower Bounds for Graph Problems}}
{{Infobox
|label1 = Proposed by
|data1 = Krzysztof Onak
|label2 = Source
|data2 = [[Workshops:Kanpur_2009|Kanpur 2009]]
|label3 = Short link
|data3 = http://sublinear.info/29
}}
A large number of streaming papers consider graph problems. Typically, the input stream is an arbitrarily-ordered sequence of edges. For many problems, one can show that solving the problem, even approximately, requires $\Omega(n)$ bits of space.
For instance, one can relatively easily prove that finding a constant-factor approximation to the maximum matching problem requires $\Omega(n)$ bits of space.
Therefore, in many cases, the desired space complexity is of the form $\tilde O(n)$. Despite this relaxation, it is plausible that for some popular problems, there are barriers that cannot be overcome by (approximate) algorithms that use $n^{1+o(1)}$ space and a small number of passes.

For example, let $M(G)$ be the maximum matching size in the input graph $G$.
McGregor {{cite|McGregor-05}} shows that there is an algorithm that finds a matching of size $(1-\epsilon) \cdot M(G)$ in a number of passes that is a function of only $\epsilon$. It is plausible that for any constant $k$, there is no $k$-pass $\tilde O(n)$-space algorithm that finds a matching of size greater than $(1-\epsilon_k) \cdot M(G)$ times the optimum, where $\epsilon_k$ is a positive constant. In particular, to the best of my knowledge, no one-pass $\tilde O(n)$-space algorithm that finds a $(1-\epsilon)$-approximation for any constant $\epsilon \in (0,1/2)$ is known. Can one prove lower bounds as suggested above?
The question generalizes to other problems.
For instance, the best known $\tilde O(n)$-space algorithms for simulating random walks require a large number of passes (see {{cite|DasSarmaGP-08}} and Rina Panigrahy's question). Can one prove for these problems that a small number of passes requires $n^{1+\Omega(1)}$ space?

To the best of my knowledge, the only problem for which this kind of lower bound is known is approximating graph distances. Feigenbaum et al. {{cite|FeigenbaumKMSZ-08}} show that obtaining a $t$-approximation for the distance between two nodes in a single pass requires $\Omega(n^{1+1/t})$ space.

← Older revision		Revision as of 21:14, 26 June 2013
Line 13:		Line 13:

	To the best of my knowledge, computing the BFS tree and computing the diameter are the only problems for which an $n^{1+\Omega(1)}$ lower bound for more than one pass is known {{cite\|FeigenbaumKMSZ-08}}.		To the best of my knowledge, computing the BFS tree and computing the diameter are the only problems for which an $n^{1+\Omega(1)}$ lower bound for more than one pass is known {{cite\|FeigenbaumKMSZ-08}}.
		+
		+	== Update ==
		+	Guruswami and Onak {{cite\|GuruswamiO-13}} showed that the following problems require roughly $n^{1+\Omega(1/p)}$ bits of space in $p$ passes: testing if there is a perfect matching, checking if $v$ and $w$ are at distance at most $2(p+1)$, and checking if there is a directed path from $v$ to $w$, where $v$ and $w$ are known to the algorithm in advance.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur09
 |who=Krzysztof Onak

@@ Line 11: / Line 11: @@
 McGregor {{cite|McGregor-05}} shows that there is an algorithm that finds a matching of size $(1-\epsilon) \cdot M(G)$ in a number of passes that is a function of only $\epsilon$. It is plausible that for any constant $k$, there is no $k$-pass $\tilde O(n)$-space algorithm that finds a matching of size greater than $(1-\epsilon_k) \cdot M(G)$ times the optimum, where $\epsilon_k$ is a positive constant. In particular, to the best of my knowledge, no one-pass $\tilde O(n)$-space algorithm that finds a $(1-\epsilon)$-approximation for any constant $\epsilon \in (0,1/2)$ is known. Can one prove lower bounds as suggested above?
 The question generalizes to other problems.
-For instance, the best known $\tilde O(n)$-space algorithms for simulating random walks require a large number of passes (see {{cite|DasSarmaGP-08}} and Rina Panigrahy's question). Can one prove for these problems that a small number of passes requires $n^{1+\Omega(1)}$ space?
+For instance, the best known $\tilde O(n)$-space algorithms for simulating random walks require a large number of passes (see {{cite|DasSarmaGP-08}} and [[Open_Problems:22|Rina Panigrahy's question]]). Can one prove for these problems that a small number of passes requires $n^{1+\Omega(1)}$ space?
-To the best of my knowledge, the only problem for which this kind of lower bound is known is approximating graph distances. Feigenbaum et al. {{cite|FeigenbaumKMSZ-08}} show that obtaining a $t$-approximation for the distance between two nodes in a single pass requires $\Omega(n^{1+1/t})$ space.
+To the best of my knowledge, computing the BFS tree and computing the diameter are the only problems for which an $n^{1+\Omega(1)}$ lower bound for more than one pass is known {{cite|FeigenbaumKMSZ-08}}.

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 29: Strong Lower Bounds for Graph Problems}}
+{{Header
-{{Infobox
+|title=Strong Lower Bounds for Graph Problems
-|label1 = Proposed by
+|source=kanpur09
-|data1 = Krzysztof Onak
+|who=Krzysztof Onak
 }}
 A large number of streaming papers consider graph problems. Typically, the input stream is an arbitrarily-ordered sequence of edges. For many problems, one can show that solving the problem, even approximately, requires $\Omega(n)$ bits of space.

← Older revision	Revision as of 05:33, 8 November 2012
(No difference)