1.7k citations · 1.9k across the 33 of their papers we have counts for
4 papers · 1 filter
Coding for interactive communication correcting insertions and deletions
Mark Braverman, Ran Gelles, Jieming Mao +1
We consider the question of interactive communication, in which two remote parties perform a computation while their communication channel is (adversarially) noisy. We extend here…
Weighted Sampling Without Replacement from Data Streams
Vladimir Braverman, Rafail Ostrovsky, Gregory Vorsanger
Weighted sampling without replacement has proved to be a very important tool in designing new algorithms. Efraimidis and Spirakis (IPL 2006) presented an algorithm for weighted sam…
A randomized online quantile summary in words
David Felber, Rafail Ostrovsky
A quantile summary is a data structure that approximates to -relative error the order statistics of a much larger underlying dataset. In this paper we develop a random…
Variability in data streams
David Felber, Rafail Ostrovsky
We consider the problem of tracking with small relative error an integer function defined by a distributed update stream . Existing streaming algorithms with worst-ca…