54 citations · 56 across the 2 of their papers we have counts for
2 papers
cs.DS2011★ 54 cited
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…
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…