1.7k citations · 1.9k across the 33 of their papers we have counts for
6 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…
Deterministic and Energy-Optimal Wireless Synchronization
Leonid Barenboim, Shlomi Dolev, Rafail Ostrovsky
We consider the problem of clock synchronization in a wireless setting where processors must power-down their radios in order to save energy. Energy efficiency is a central goal in…
Position-Based Quantum Cryptography: Impossibility and Constructions
Harry Buhrman, Nishanth Chandran, Serge Fehr +4
In this work, we study position-based cryptography in the quantum setting. The aim is to use the geographical position of a party as its only credential. On the negative side, we s…
Position-Based Quantum Cryptography
Nishanth Chandran, Serge Fehr, Ran Gelles +2
This paper is replaced by arXiv:1009.2490. The new paper includes a general impossibility result and restricted possibility results, and it has two additional authors.