Open Problems:32 - Revision history

Krzysztof Onak: updated header

2013-03-07T01:51:36Z

updated header

Krzysztof Onak at 05:25, 16 November 2012

2012-11-16T05:25:57Z

Krzysztof Onak: 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..."

2012-11-13T01:28:05Z

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..."

New page

{{DISPLAYTITLE:Problem 32: The Value of a Reverse Pass}}
{{Infobox
|label1 = Proposed by
|data1 = Andrew McGregor
|label2 = Source
|data2 = [[Workshops:Kanpur_2009|Kanpur 2009]]
|label3 = Short link
|data3 = http://sublinear.info/32
}}
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?

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur09
 |who=Andrew McGregor

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 32: The Value of a Reverse Pass}}
+{{Header
-{{Infobox
+|title=The Value of a Reverse Pass
-|label1 = Proposed by
+|source=kanpur09
-|data1 = Andrew McGregor
+|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
 &ldquo;${\tt (}$,${\tt )}$,${\tt [}$,${\tt ]}$&rdquo;, 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?