Quantitative relation between noise sensitivity and influences (Q2448963): Difference between revisions

A Boolean function \(f\) of \(n\) variables is said to be noise sensitive if inserting a small random error in its argument makes the value of the function almost unpredictable. \textit{I. Benjamini} et al. [Publ. Math., Inst. Hautes Étud. Sci. 90, 5--43 (1999; Zbl 0986.60002)] showed that if the sum of squares of influences of \(f\) is close to zero then \( f\) must be noise sensitive. In this paper a quantitative version of this result which does not depend on \(n\) is proved; it is tight for certain parameters. These results hold also for a general product measure \(\mu_{p}\) on the discrete cube, as long as \(\log 1/p \ll \log n\). Note that in the quoted paper, a quantitative relation between the sum of squares of the influences and the noise sensitivity was also shown, but only when the sum of squares is bounded by \(n^{-c}\) for a constant \(c\). The authors also propose a generalization of a lemma of \textit{M. Talagrand} [Combinatorica 16, No. 2, 243--258 (1996; Zbl 0861.05008)] on the Fourier coefficients of monotone Boolean functions and present a considerably shorter proof of it, which easily generalizes in various directions, including non-monotone functions.