54 citations · 57 across the 5 of their papers we have counts for
5 papers · 1 filter
A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support
Akashnil Dutta, Reut Levi, Dana Ron +1
We present a simple adaptation of the Lempel Ziv 78' (LZ78) compression scheme ({\em IEEE Transactions on Information Theory, 1978}) that supports efficient random access to the in…
Fast Local Computation Algorithms
Ronitt Rubinfeld, Gil Tamir, Shai Vardi +1
For input , let denote the set of outputs that are the "legal" answers for a computational problem . Suppose and members of are so large that there is not t…
Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity
Dana Ron, Ronitt Rubinfeld, Muli Safra +1
The {\em Total Influence} ({\em Average Sensitivity) of a discrete function is one of its fundamental measures. We study the problem of approximating the total influence of a monot…
Sublinear Time Algorithms for Earth Mover's Distance
Khanh Do Ba, Huy L Nguyen, Huy N Nguyen +1
We study the problem of estimating the Earth Mover's Distance (EMD) between probability distributions when given access only to samples. We give closeness testers and additive-erro…
Sublinear Algorithms for Approximating String Compressibility
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld +1
We raise the question of approximating the compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popul…