Difference between revisions of "Open Problems:44"
(Created page with "{{Header |title=Approximating LIS Length in the Streaming Model |source=bertinoro11 |who=Amit Chakrabarti }} The goal of LIS is to compute a $2$-approximation of the length of...") |
m (updated header) |
||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|source=bertinoro11 | |source=bertinoro11 | ||
|who=Amit Chakrabarti | |who=Amit Chakrabarti | ||
Latest revision as of 01:54, 7 March 2013
| Suggested by | Amit Chakrabarti |
|---|---|
| Source | Bertinoro 2011 |
| Short link | https://sublinear.info/44 |
The goal of LIS is to compute a $2$-approximation of the length of the longest increasing subsequence in a given stream of elements.
Question: What is the randomized streaming space complexity of LIS, for one pass or possibly a constant number of passes?
Background: Gopalan et al. [GopalanJKK-07] gave an $O(n^{1/2} \operatorname{polylog}(n))$-space deterministic streaming algorithm, using one pass, that achieves $c$-approximation for any fixed $c>0$. For deterministic algorithms [GalG-07,ErgunJ-08] showed an $\Omega(n^{1/2})$ space lower bound, for a constant number of passes. The latter arguments proceed by proving a lower bound for related communication complexity problems. However, it is known that the randomized communication complexity of those problem is $O(\log n)$ [Chakrabarti-10] so a different approach is needed.
