3 citations · 3 across the 2 of their papers we have counts for
3 papers
cs.DS2009★ 3 cited
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…
cs.DS2008
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…
cs.DS2008
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…