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:{±1}n⟶{±1}, \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 % Ω(I[f]n/logn)Ω(logn⋅I[f]n) on the query complexity of any constant-factor approximation algorithm for this problem (which holds for I[f]=Ω(1)), % and I[f]=O(n/logn)), hence showing that our algorithm is almost optimal in terms of its dependence on n. For general functions we give a lower bound of Ω(I[f]n), which matches the complexity of a simple sampling algorithm.
The Total Influence ( 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, 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 ± ε ) by performing O (√ n I [ f ] poly(1/ ε )) queries. We also prove a lower bound of Ω (√ n log n · I [ f ]) on the query complexity of any constant factor approximation algorithm for this problem (which holds for I [ f ]= Ω (1)), hence showing that our algorithm is almost optimal in terms of its dependence on n . For general functions, we give a lower bound of Ω ( n I [ f ]), which matches the complexity of a simple sampling algorithm.
We prove that, to compute a Boolean function f on N variables with error probability ε, any quantum black-box algorithm has to query at least 21−2ερfN=21−2εSˉf times, where ρf is the average influence of variables in f, and Sˉf is the average sensitivity. It's interesting to contrast this result with the known lower bound of Ω(Sf), where Sf is the sensitivity of f. This lower bound is tight for some functions. We also show for any polynomial f~ that approximates f with error probability ε, deg(f~)≥1/4(1−1+ε3ε)2ρfN. This bound can be better than previous known lower bound of Ω(BSf) for some functions. Our technique may be of intest itself: we apply Fourier analysis to functions mapping {0,1}N to unit vectors in a Hilbert space. From this viewpoint, the state of the quantum computer at step t can be written as ∑s∈{0,1}N,∣s∣≤tϕ^s(−1)s⋅x, which is handy for lower bound analysis.