28 citations · 325 across the 73 of their papers we have counts for
3 papers · 1 filter
How to Catch L_2-Heavy-Hitters on Sliding Windows
Vladimir Braverman, Ran Gelles, Rafail Ostrovsky
Finding heavy-elements (heavy-hitters) in streaming data is one of the central, and well-understood tasks. Despite the importance of this problem, when considering the sliding wind…
Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform
Vladimir Braverman, Rafail Ostrovsky, Yuval Rabani
The celebrated dimension reduction lemma of Johnson and Lindenstrauss has numerous computational and other applications. Due to its application in practice, speeding up the computa…
Recursive Sketching For Frequency Moments
Vladimir Braverman, Rafail Ostrovsky
In a ground-breaking paper, Indyk and Woodruff (STOC 05) showed how to compute (for ) in space complexity $O(\mbox{\em poly-log}(n,m)\cdot n^{1-\frac2k})$, which is opti…