Difference between revisions of "Open Problems:32"
(Created page with "{{DISPLAYTITLE:Problem 32: The Value of a Reverse Pass}} {{Infobox |label1 = Proposed by |data1 = Andrew McGregor |label2 = Source |data2 = [[Workshops:Kanpur_2009|Kanpur 2009...") |
|||
| Line 1: | Line 1: | ||
| − | {{ | + | {{Header |
| − | + | |title=The Value of a Reverse Pass | |
| − | | | + | |source=kanpur09 |
| − | | | + | |who=Andrew McGregor |
| − | |||
| − | |||
| − | |||
| − | |||
}} | }} | ||
Multi-pass stream algorithms have been designed for a range of problems including longest increasing subsequences {{cite|LibenNowellVZ-06|GuhaM-08}}, graph matchings {{cite|McGregor-05}}, and various geometric problems {{cite|ChanC-07}}. However, the existing literature almost exclusively considers the case when the multiple passes are in the same direction. One exception is recent work by Magniez et al. {{cite|MagniezMN-10}} on the '''DYCK'''${}_2$ problem: given a length $n$ string in the alphabet | Multi-pass stream algorithms have been designed for a range of problems including longest increasing subsequences {{cite|LibenNowellVZ-06|GuhaM-08}}, graph matchings {{cite|McGregor-05}}, and various geometric problems {{cite|ChanC-07}}. However, the existing literature almost exclusively considers the case when the multiple passes are in the same direction. One exception is recent work by Magniez et al. {{cite|MagniezMN-10}} on the '''DYCK'''${}_2$ problem: given a length $n$ string in the alphabet | ||
“${\tt (}$,${\tt )}$,${\tt [}$,${\tt ]}$”, determine whether it is well-parenthesized, i.e., it can be generated by the grammar $S\rightarrow {\tt (}S{\tt)} ~|~ {\tt [}S{\tt]} ~|~ SS ~|~ \epsilon$? For this problem it can be shown that with one forward and one reverse pass over the input, the problem can be solved with $O(\log^2 n)$ space. On the other hand, any algorithm using $O(1)$ forward passes and no reverse passes, requires $\Omega(\sqrt{n})$ space {{cite|ChakrabartiCKM-10|JainN-10}}. For what other natural problems is there such a large separation? | “${\tt (}$,${\tt )}$,${\tt [}$,${\tt ]}$”, determine whether it is well-parenthesized, i.e., it can be generated by the grammar $S\rightarrow {\tt (}S{\tt)} ~|~ {\tt [}S{\tt]} ~|~ SS ~|~ \epsilon$? For this problem it can be shown that with one forward and one reverse pass over the input, the problem can be solved with $O(\log^2 n)$ space. On the other hand, any algorithm using $O(1)$ forward passes and no reverse passes, requires $\Omega(\sqrt{n})$ space {{cite|ChakrabartiCKM-10|JainN-10}}. For what other natural problems is there such a large separation? | ||
Revision as of 05:25, 16 November 2012
| Suggested by | Andrew McGregor |
|---|---|
| Source | Kanpur 2009 |
| Short link | https://sublinear.info/32 |
Multi-pass stream algorithms have been designed for a range of problems including longest increasing subsequences [LibenNowellVZ-06,GuhaM-08], graph matchings [McGregor-05], and various geometric problems [ChanC-07]. However, the existing literature almost exclusively considers the case when the multiple passes are in the same direction. One exception is recent work by Magniez et al. [MagniezMN-10] on the DYCK${}_2$ problem: given a length $n$ string in the alphabet “${\tt (}$,${\tt )}$,${\tt [}$,${\tt ]}$”, determine whether it is well-parenthesized, i.e., it can be generated by the grammar $S\rightarrow {\tt (}S{\tt)} ~|~ {\tt [}S{\tt]} ~|~ SS ~|~ \epsilon$? For this problem it can be shown that with one forward and one reverse pass over the input, the problem can be solved with $O(\log^2 n)$ space. On the other hand, any algorithm using $O(1)$ forward passes and no reverse passes, requires $\Omega(\sqrt{n})$ space [ChakrabartiCKM-10,JainN-10]. For what other natural problems is there such a large separation?
