54 citations · 57 across the 5 of their papers we have counts for
Showing 2011 · cs.DSShow all
2 papers · 2 filters
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…