Computer Science – Data Structures and Algorithms
Scientific paper
2011-01-27
Computer Science
Data Structures and Algorithms
Scientific paper
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 monotone Boolean function \ifnum\plusminus=1 $f: \{\pm1\}^n \longrightarrow \{\pm1\}$, \else $f: \bitset^n \to \bitset$, \fi which we denote by $I[f]$. We present a randomized algorithm that approximates the influence of such functions to within a multiplicative factor of $(1\pm \eps)$ by performing $O(\frac{\sqrt{n}\log n}{I[f]} \poly(1/\eps)) $ queries. % \mnote{D: say something about technique?} We also prove a lower bound of % $\Omega(\frac{\sqrt{n/\log n}}{I[f]})$ $\Omega(\frac{\sqrt{n}}{\log n \cdot I[f]})$ on the query complexity of any constant-factor approximation algorithm for this problem (which holds for $I[f] = \Omega(1)$), % and $I[f] = O(\sqrt{n}/\log n)$), hence showing that our algorithm is almost optimal in terms of its dependence on $n$. For general functions we give a lower bound of $\Omega(\frac{n}{I[f]})$, which matches the complexity of a simple sampling algorithm.
Ron Dana
Rubinfeld Ronitt
Safra Muli
Weinstein Omri
No associations
LandOfFree
Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-545809