A note on randomized streaming space bounds for the longest increasing subsequence problem

DOI10.1016/J.IPL.2011.12.008zbMath1237.68086OpenAlexW2074139744MaRDI QIDQ413292

Amit Chakrabarti

Publication date: 4 May 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.12.008

zbMATH Keywords

lower boundscommunication complexitydata streamslongest increasing subsequence

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

On the monotonicity of a data stream

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Private vs. common random bits in communication complexity
• The space complexity of approximating the frequency moments
• Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence

This page was built for publication: A note on randomized streaming space bounds for the longest increasing subsequence problem