Quantitative relation between noise sensitivity and influences |
| |
Authors: | Nathan Keller Guy Kindler |
| |
Institution: | 1. Faculty of Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, Israel 2. Incumbent of the Harry and Abe Sherman Lectureship, Chair at the Hebrew Univeristy of Jerusalem, Jerusalem, Israel
|
| |
Abstract: | A Boolean function f: {0,1} n → {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 3] showed that if the sum of squares of inuences of 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 µ p on the discrete cube, as long as log1/p?logn. We note that in 3], a quantitative relation between the sum of squares of the inuences 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|