Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence.

Anna Gál Parikshit Gopalan

Published in: FOCS (2007)

Keyphrases

lower bound
upper bound
worst case
orders of magnitude
data structure
theoretical analysis
lower and upper bounds
running times
real time
online algorithms
upper and lower bounds
times faster
pattern matching
similarity search
computationally efficient
computational complexity
objective function