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.
We give a {\em deterministic} algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-2 polynomial threshold function. Given a degree-2 input polynomial p(x1,…,xn) and a parameter $\eps > 0$, the algorithm approximates Prx∼{−1,1}n[p(x)≥0] to within an additive $\pm \eps$ in time $\poly(n,2^{\poly(1/\eps)})$. Note that it is NP-hard to determine whether the above probability is nonzero, so any sort of multiplicative approximation is almost certainly impossible even for efficient randomized algorithms. This is the first deterministic algorithm for this counting problem in which the running time is polynomial in n for $\eps= o(1)$. For "regular" polynomials p (those in which no individual variable's influence is large compared to the sum of all n variable influences) our algorithm runs in $\poly(n,1/\eps)$ time. The algorithm also runs in $\poly(n,1/\eps)$ time to approximate Prx∼N(0,1)n[p(x)≥0] to within an additive $\pm \eps$, for any degree-2 polynomial p. As an application of our counting result, we give a deterministic FPT multiplicative $(1 \pm \eps)$-approximation algorithm to approximate the k-th absolute moment $\E_{x \sim \{-1,1\}^n}[|p(x)^k|]$ of a degree-2 polynomial. The algorithm's running time is of the form $\poly(n) \cdot f(k,1/\eps)$.