Best-order streaming model

DOI10.1016/j.tcs.2010.10.046zbMath1216.68108OpenAlexW2131726773MaRDI QIDQ534570

Danupon Nanongkai, Atish Das Sarma, Richard J. Lipton

Publication date: 18 May 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.10.046

zbMATH Keywords

communication complexitydata streammodel of computation

Mathematics Subject Classification ID

Uses Software

• Amazon EC2

Cites Work

• Communication complexity
• Selection and sorting with limited storage
• The communication complexity of several problems in matrix computation
• Results on communication complexity classes
• The space complexity of approximating the frequency moments
• Streaming graph computations with a helpful advisor
• On graph problems in a semi-streaming model
• Proof verification and the hardness of approximation problems
• Annotations in Data Streams
• Probabilistic checking of proofs
• Communication Complexity
• Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming
• The PCP theorem by gap amplification
• Trading off space for passes in graph streaming problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Best-order streaming model