期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The deterministic space complexity of approximating the length of the longest increasing subsequence of
a stream of N integers is known to be (N) . However, the randomized
complexity is wide open. We show that the technique used in earlier work to establish the (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.
