25 citations · 49 across the 16 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
cs.DS2011
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…
cs.DS2011★ 2 cited
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…