In 1994, Talagrand showed a generalization of the celebrated KKL theorem. In this work, we prove that the converse of this generalization also holds. Namely, for any sequence of numbers $0<a_1,a_2,ldots,a_nle 1$ such that $sum_{j=1}^n a_j/(1-log a_j)
ge C$ for some constant $C>0$, it is possible to find a roughly balanced Boolean function $f$ such that $textrm{Inf}_j[f] < a_j$ for every $1 le j le n$.
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 ifnumplusminus=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 $(1pm 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.
