Publications (30)
Matrix Balancing in Lp Norms: A New Analysis of Osborne's Iteration
Rafail Ostrovsky, Yuval Rabani, Arman Yousefi
Position-Based Quantum Cryptography
Nishanth Chandran, Serge Fehr, Ran Gelles +2
Weighted Sampling Without Replacement from Data Streams
Vladimir Braverman, Rafail Ostrovsky, Gregory Vorsanger
Near-Optimal Radio Use For Wireless Network Synchronization
Milan Bradonjic, Eddie Kohler, Rafail Ostrovsky
AMS Without 4-Wise Independence on Product Domains
Vladimir Braverman, Kai-Min Chung, Zhenming Liu +2
On The Communication Complexity of Finding an (Approximate) Stable Marriage
Rafail Ostrovsky, Will Rosenbaum
A Stable Marriage Requires Communication
Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky +1
Local Correctability of Expander Codes
Brett Hemenway, Rafail Ostrovsky, Mary Wootters
Approximating Large Frequency Moments with Pick-and-Drop Sampling
Vladimir Braverman, Rafail Ostrovsky
Fast distributed almost stable marriages
Rafail Ostrovsky, Will Rosenbaum
Secure End-to-End Communication with Optimal Throughput in Unreliable Networks
Paul Bunn, Rafail Ostrovsky
Position-Based Quantum Cryptography: Impossibility and Constructions
Harry Buhrman, Nishanth Chandran, Serge Fehr +4
Deterministic and Energy-Optimal Wireless Synchronization
Leonid Barenboim, Shlomi Dolev, Rafail Ostrovsky
Succinct Sampling on Streams
Vladimir Braverman, Rafail Ostrovsky, Carlo Zaniolo
Space-Time Tradeoffs for Distributed Verification
Rafail Ostrovsky, Mor Perry, Will Rosenbaum
Universal Streaming
Vladimir Braverman, Rafail Ostrovsky, Alan Roytman
Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform
Vladimir Braverman, Rafail Ostrovsky, Yuval Rabani
It's Not Easy Being Three: The Approximability of Three-Dimensional Stable Matching Problems
Rafail Ostrovsky, Will Rosenbaum
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin +1
Recursive Sketching For Frequency Moments
Vladimir Braverman, Rafail Ostrovsky
Throughput in Asynchronous Networks
Paul Bunn, Rafail Ostrovsky
How Hard is Counting Triangles in the Streaming Model
Vladimir Braverman, Rafail Ostrovsky, Dan Vilenchik
Coding for interactive communication correcting insertions and deletions
Mark Braverman, Ran Gelles, Jieming Mao +1
Population stability: regulating size in the presence of an adversary
Shafi Goldwasser, Rafail Ostrovsky, Alessandra Scafuro +1
A randomized online quantile summary in $O(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon})$ words
David Felber, Rafail Ostrovsky
Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration
Rafail Ostrovsky, Yuval Rabani, Arman Yousefi
Improved Approximation Algorithms for Earth-Mover Distance in Data Streams
Arman Yousefi, Rafail Ostrovsky
How to Catch L_2-Heavy-Hitters on Sliding Windows
Vladimir Braverman, Ran Gelles, Rafail Ostrovsky
Measuring Independence of Datasets
Vladimir Braverman, Rafail Ostrovsky
Variability in data streams
David Felber, Rafail Ostrovsky