Best-order streaming model

DOI10.1016/J.TCS.2010.10.046zbMATH Open1216.68108OpenAlexW2131726773MaRDI QIDQ534570FDOQ534570

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

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

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)

Cites Work

• The space complexity of approximating the frequency moments
• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• 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.
• Communication Complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• On graph problems in a semi-streaming model
• Communication complexity
• The randomized communication complexity of set disjointness
• Annotations in Data Streams
• Title not available (Why is that?)
• Selection and sorting with limited storage
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph distances in the streaming model: the value of space
• Title not available (Why is that?)
• Title not available (Why is that?)
• The PCP theorem by gap amplification
• Trading off space for passes in graph streaming problems
• Title not available (Why is that?)
• The communication complexity of several problems in matrix computation
• Results on communication complexity classes
• Title not available (Why is that?)
• Finding duplicates in a data stream
• Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming

Cited In (1)

• Best-Order Streaming Model

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)