The communication and streaming complexity of computing the longest common and increasing subsequences

MaRDI QIDQ2934612zbMATH OpenFDO

Authors Xiaoming Sun, David P. Woodruff

Publication date 18 December 2014

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Computing and Combinatorics
• Finding longest increasing and common subsequences in streaming data
• Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
• A note on randomized streaming space bounds for the longest increasing subsequence problem
• Fast computation of a longest increasing subsequence and application

Cited in

(14)

• scientific article; zbMATH DE number 7559139 (Why is no real title available?)
• Communication-Efficient Private Protocols for Longest Common Subsequence
• A note on randomized streaming space bounds for the longest increasing subsequence problem
• Fast and longest rollercoasters
• Computing and Combinatorics
• scientific article; zbMATH DE number 7561345 (Why is no real title available?)
• Streaming and query once space complexity of longest increasing subsequence
• Space-efficient algorithms for longest increasing subsequence
• Space-efficient algorithms for longest increasing subsequence
• Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
• On the monotonicity of a data stream
• Estimating the longest increasing sequence in polylogarithmic time
• Compressed communication complexity of longest common prefixes
• Finding longest increasing and common subsequences in streaming data

This page was built for publication: The communication and streaming complexity of computing the longest common and increasing subsequences

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