Editing Open Problems:29
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| Line 1: | Line 1: | ||
| − | {{ | + | {{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. | 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. | ||
| Line 10: | Line 15: | ||
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? | 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. | 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 | + | 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, | + | 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. |
| − | |||
| − | |||
| − | |||
