Best-order streaming model

DOI10.1016/J.TCS.2010.10.046MaRDI QIDQ534570zbMATH OpenOpenAlexFDO

Authors Atish Das Sarma, Richard J. Lipton, Danupon Nanongkai

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

data streamcommunication complexitymodel of computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Best-Order Streaming Model
• Streaming computations with a loquacious prover
• Streaming verification of graph properties
• Testable bounded degree graph properties are random order streamable
• Estimating graph parameters from random order streams

Cites work

• scientific article; zbMATH DE number 4205986 (Why is no real title available?)
• scientific article; zbMATH DE number 5485522 (Why is no real title available?)
• scientific article; zbMATH DE number 5764792 (Why is no real title available?)
• scientific article; zbMATH DE number 1142305 (Why is no real title available?)
• scientific article; zbMATH DE number 1542661 (Why is no real title available?)
• scientific article; zbMATH DE number 1792102 (Why is no real title available?)
• scientific article; zbMATH DE number 1424324 (Why is no real title available?)
• scientific article; zbMATH DE number 1445300 (Why is no real title available?)
• scientific article; zbMATH DE number 5485578 (Why is no real title available?)
• Annotations in Data Streams
• Communication Complexity
• Communication complexity
• Finding duplicates in a data stream
• Graph distances in the streaming model: the value of space
• Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming
• On graph problems in a semi-streaming model
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Results on communication complexity classes
• Selection and sorting with limited storage
• The PCP theorem by gap amplification
• The art of computer programming. Vol. 4, Fasc. 0--4. Fasc. 0: Introduction to combinatorial algorithms and Boolean functions. Fasc. 1: Bitwise tricks \& techniques, binary decision diagrams. Fasc. 2: Generating all tuples and permutations. Fasc. 3: Generating all combinations and partitions. Fasc. 4: Generating all trees. History of combinatorial generation.
• The communication complexity of several problems in matrix computation
• The randomized communication complexity of set disjointness
• The space complexity of approximating the frequency moments
• Trading off space for passes in graph streaming problems

Cited in

(1)

• Best-Order Streaming Model

Describes a project that uses

Uses Software

• Amazon EC2

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

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