3 citations · 3 across the 2 of their papers we have counts for
3 papers · 1 filter
A Near-Optimal Algorithm for L1-Difference
Jelani Nelson, David P. Woodruff
We give the first L_1-sketching algorithm for integer vectors which produces nearly optimal sized sketches in nearly linear time. This answers the first open problem in the list of…
Revisiting Norm Estimation in Data Streams
Daniel M. Kane, Jelani Nelson, David P. Woodruff
The problem of estimating the pth moment F_p (p nonnegative and real) in data streams is as follows. There is a vector x which starts at 0, and many updates of the form x_i <-- x_i…
Sketching and Streaming Entropy via Approximation Theory
Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak
We conclude a sequence of work by giving near-optimal sketching and streaming algorithms for estimating Shannon entropy in the most general streaming model, with arbitrary insertio…