Stochastic streams: sample complexity vs. space complexity

DOI10.4230/LIPICS.ESA.2016.32zbMATH Open1397.68095MaRDI QIDQ4606301FDOQ4606301

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

Publication date: 2 March 2018

Recommendations

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

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)

Cited In (4)

• Two Party Distribution Testing: Communication and Security
• Title not available (Why is that?)
• (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond
• Revisiting frequency moment estimation in random order streams

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)