Quantitative relation between noise sensitivity and influences

Details Quantitative relation between noise sensitivity and influences Quantitative relation between noise sensitivity and influences

2010-03-09

arxiv.org/abs/1003.1839v1

Mathematics

Combinatorics

20 pages

Scientific paper

A Boolean function $f:\{0,1\}^n \to \{0,1\}$ is said to be noise sensitive if inserting a small random error in its argument makes the value of the function almost unpredictable. Benjamini, Kalai and Schramm showed that if the sum of squares of influences in $f$ is close to zero then $f$ must be noise sensitive. We show a quantitative version of this result which does not depend on $n$, and prove that it is tight for certain parameters. Our results hold also for a general product measure $\mu_p$ on the discrete cube, as long as $\log 1/p \ll \log n$. We note that in [BKS], 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$. Our results require a generalization of a lemma of Talagrand on the Fourier coefficients of monotone Boolean functions. In order to achieve it, we present a considerably shorter proof of Talagrand's lemma, which easily generalizes in various directions, including non-monotone functions.

Affiliated with

Also associated with

No associations

Rating

Quantitative relation between noise sensitivity and influences 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 Quantitative relation between noise sensitivity and influences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantitative relation between noise sensitivity and influences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-454827