1.7k citations · 1.8k across the 5 of their papers we have counts for
6 papers
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…
Throughput in Asynchronous Networks
Paul Bunn, Rafail Ostrovsky
We introduce a new, "worst-case" model for an asynchronous communication network and investigate the simplest (yet central) task in this model, namely the feasibility of end-to-end…
Measuring Independence of Datasets
Vladimir Braverman, Rafail Ostrovsky
A data stream model represents setting where approximating pairwise, or -wise, independence with sublinear memory is of considerable importance. In the streaming model the joint…
Authenticated Adversarial Routing
Yair Amir, Paul Bunn, Rafail Ostrovksy
The aim of this paper is to demonstrate the feasibility of authenticated throughput-efficient routing in an unreliable and dynamically changing synchronous network in which the maj…
Succinct Sampling on Streams
Vladimir Braverman, Rafail Ostrovsky, Carlo Zaniolo
A streaming model is one where data items arrive over long period of time, either one item at a time or in bursts. Typical tasks include computing various statistics over a sliding…
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin +1
We provide formal definitions and efficient secure techniques for - turning noisy information into keys usable for any cryptographic application, and, in particular, - reliably and…