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

DOI10.1016/J.IPL.2011.12.008zbMATHOpenAlexMaRDI QIDQ413292FDO

Authors 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 boundsdata streamscommunication complexitylongest increasing subsequence

Mathematics Subject Classification ID

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

Recommendations

• Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
• The communication and streaming complexity of computing the longest common and increasing subsequences
• Computing and Combinatorics
• Finding longest increasing and common subsequences in streaming data
• Estimating the sortedness of a data stream

Cites work

• scientific article; zbMATH DE number 5764793 (Why is no real title available?)
• Data streams: algorithms and applications.
• Estimating the sortedness of a data stream
• Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
• Private vs. common random bits in communication complexity
• The space complexity of approximating the frequency moments

Cited in

(3)

• Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
• On the monotonicity of a data stream
• The communication and streaming complexity of computing the longest common and increasing subsequences

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q413292)