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

DOI10.1137/090770801zbMath1209.68258OpenAlexW2018407082MaRDI QIDQ5390602

Anna Gál, Parikshit Gopalan

Publication date: 4 April 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/090770801

zbMATH Keywords

communication complexitystreaming algorithmslongest increasing subsequencedirect sum problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

On the monotonicity of a data stream ⋮ Space-Efficient Algorithms for Longest Increasing Subsequence ⋮ A note on randomized streaming space bounds for the longest increasing subsequence problem ⋮ Space-efficient algorithms for longest increasing subsequence ⋮ Estimating the Longest Increasing Sequence in Polylogarithmic Time ⋮ Unnamed Item ⋮ Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy ⋮ Unnamed Item

This page was built for publication: Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence