3 citations · 5 across the 4 of their papers we have counts for
4 papers
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
Reut Levi, Dana Ron
Motivated by the problem of testing planarity and related properties, we study the problem of designing efficient {\em partition oracles}. A {\em partition oracle} is a procedure t…
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…
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 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…