The Space Complexity of Approximating the Frequency Moments

Noga Alon, Yossi Matias, Márió Szegedy

Type: Article

Publication Date: 1999-02-01

Citations: 1205

DOI: https://doi.org/10.1006/jcss.1997.1545

View Publication

Locations

Journal of Computer and System Sciences - View

Similar Works

Action	Title	Year	Authors
+	Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors	2016	Vladimir Braverman Stephen R. Chestnut David P. Woodruff Lin F. Yang
+	The quantum complexity of approximating the frequency moments	2016	MontanaroAshley
+	Approximating Large Frequency Moments with $O(n^{1-2/k})$ Bits	2014	Vladimir Braverman Jonathan Katzman Charles Seidell Gregory Vorsanger
+	Approximating Large Frequency Moments with Pick-and-Drop Sampling	2012	Vladimir Braverman Rafail Ostrovsky
+	Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors	2016	Vladimir Braverman Stephen R. Chestnut David P. Woodruff Lin F. Yang
+	Taylor Polynomial Estimator for Estimating Frequency Moments	2015	Šumit Ganguly
+	Taylor Polynomial Estimator for Estimating Frequency Moments	2015	Šumit Ganguly
+	The quantum complexity of approximating the frequency moments	2015	Ashley Montanaro
+	The quantum complexity of approximating the frequency moments	2015	Ashley Montanaro
+	Streaming sums in sublinear space.	2014	Vladimir Braverman Stephen R. Chestnut
+ PDF Chat	Optimality of Frequency Moment Estimation	2024	Mark Braverman Or Zamir
+ PDF Chat	The quantum complexity of approximating the frequency moments	2016	Ashley Montanaro
+	A Lower Bound for Estimating High Moments of a Data Stream	2012	Šumit Ganguly
+	A Streaming Approximation Algorithm for Klee's Measure Problem	2010	Gokarna Sharma Costas Busch Srikanta Tirthapura
+	Universal sketches for the frequency negative moments and other decreasing streaming sums	2014	Vladimir Braverman Stephen R. Chestnut
+ PDF Chat	Frequency Estimation with One-Sided Error	2022	Piotr Indyk Shyam Narayanan David P. Woodruff
+	Zero-one frequency laws	2010	Vladimir Braverman Rafail Ostrovsky
+ PDF Chat	An optimal lower bound on the communication complexity of gap-hamming-distance	2011	Amit Chakrabarti Oded Regev
+	Estimating small moments of data stream in nearly optimal space-time	2010	Šumit Ganguly
+	Compressed Counting	2008	Ping Li

Works That Cite This (476)

Action	Title	Year	Authors
+ PDF Chat	Probabilistic Counters for Privacy Preserving Data Aggregation	2022	Marek Klonowski Dominik Bojko Krzysztof Grining
+	On the estimation of the mean of a random vector	2017	Émilien Joly Gábor Lugosi Roberto I. Oliveira
+	Learning from MOM’s principles: Le Cam’s approach	2018	Guillaume Lecué Matthieu Lerasle
+ PDF Chat	Approximating the Caro-Wei Bound for Independent Sets in Graph Streams	2018	Graham Cormode Jacques Dark Christian Konrad
+ PDF Chat	Robust classification via MOM minimization	2020	Guillaume Lecué Matthieu Lerasle Timlothée Mathieu
+	Sample Complexity Bounds for Influence Maximization	2019	Gal Sadeh Edith Cohen Haim Kaplan
+	Robust statistical learning with Lipschitz and convex loss functions	2019	Geoffrey Chinot Guillaume Lecué Matthieu Lerasle
+ PDF Chat	Combining geometry and combinatorics: A unified approach to sparse signal recovery	2008	Radu Berinde Anna C. Gilbert Piotr Indyk Howard Karloff Michael Strauss
+	Memory-Sample Tradeoffs for Linear Regression with Small Error	2019	Vatsal Sharan Aaron Sidford Gregory Valiant
+	A Derandomized Sparse Johnson-Lindenstrauss Transform	2010	Daniel M. Kane Jelani Nelson

Works Cited by This (2)

Action	Title	Year	Authors
+	A fast and simple randomized parallel algorithm for the maximal independent set problem	1986	Noga Alon László Babai Alon Itai
+	Lower bounds by probabilistic arguments	1983	Andrew Chi-Chih Yao