Optimal space lower bounds for all frequency moments

191 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022, background): “This type of lower bound over a subrange of 𝑀 is common in the streaming algorithms literature [92].”
An improved data stream summary: the count-min sketch and its applications (2004, background): “But accurate estimation of the L2 norm of a stream requires Ω( 1 ε(2) ) space [30].”
Tight bounds for distributed functional monitoring (2011, background): “Implications for the Data Stream Model: In 2003, Indyk and Woodruff introduced the GHD problem [34], where a1-round lower bound shortly followed [50].”
Handbook of Big Data (2016, background): “For example, one can prove that the Hamming sketch from above is optimal [62,64,94].”
An optimal algorithm for the distinct elements problem (2010, background): “The problem of space-efficient F0-estimation is well-studied, beginning with the work of Flajolet and Martin [20], and continuing with a long line of research, [3, 4, 5, 6, 9, 12, 16, 17, 19, 23, 24, 26, 36].”
An optimal lower bound on the communication complexity of gap-hamming-distance (2010, methodology): “Woodruff [Woo04] soon followed up with an Ω ( n ) bound for GHD itself, still in the one-way model; the proof used rather intricate combinatorial constructions and computations.”