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

DOI10.1016/J.IPL.2011.12.008zbMATH Open1237.68086OpenAlexW2074139744MaRDI QIDQ413292FDOQ413292

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

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

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)

Cites Work

• The space complexity of approximating the frequency moments
• Data streams: algorithms and applications.
• Private vs. common random bits in communication complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence

Cited In (2)

• Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
• On the monotonicity of a data stream

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)