54 citations · 138 across the 46 of their papers we have counts for
4 papers · 1 filter
A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size
Krzysztof Onak, Dana Ron, Michal Rosen +1
We give a nearly optimal sublinear-time algorithm for approximating the size of a minimum vertex cover in a graph G. The algorithm may query the degree deg(v) of any vertex v of it…
Space-efficient Local Computation Algorithms
Noga Alon, Ronitt Rubinfeld, Shai Vardi +1
Recently Rubinfeld et al. (ICS 2011, pp. 223--238) proposed a new model of sublinear algorithms called \emph{local computation algorithms}. In this model, a computation problem …
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…