Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-100 | 25th June 2010 01:56

A Note on Randomized Streaming Space Bounds for the Longest Increasing Subsequence Problem

RSS-Feed




TR10-100
Authors: Amit Chakrabarti
Publication: 25th June 2010 08:45
Downloads: 1416
Keywords: 


Abstract:

The deterministic space complexity of approximating the length of the longest increasing subsequence of
a stream of $N$ integers is known to be $\widetilde{\Theta}(\sqrt N)$. However, the randomized
complexity is wide open. We show that the technique used in earlier work to establish the $\Omega(\sqrt
N)$ deterministic lower bound fails strongly under randomization: specifically, we show that the
communication problems on which the lower bound is based have very efficient randomized protocols.
The purpose of this note is to guide and alert future researchers working on this very interesting problem.



ISSN 1433-8092 | Imprint