Stochastic streams: sample complexity vs. space complexity

DOI10.4230/LIPICS.ESA.2016.32MaRDI QIDQ4606301zbMATH OpenFDO

Authors Michael S. Crouch, Andrew McGregor, Gregory Valiant, David P. Woodruff

Publication date 2 March 2018

zbMATH Keywords

data streamsfrequency momentsgraph connectivitysample complexitysubspace approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Streaming Algorithms Measured in Terms of the Computed Quantity
• Sampling algorithms: lower bounds and applications
• Sampling from Dense Streams without Penalty

Cited in

(4)

• (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond
• Revisiting frequency moment estimation in random order streams
• scientific article; zbMATH DE number 7758323 (Why is no real title available?)
• Two Party Distribution Testing: Communication and Security

This page was built for publication: Stochastic streams: sample complexity vs. space complexity

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