Quantitative relation between noise sensitivity and influences
Quantitative relation between noise sensitivity and influences
复制标题
噪声敏感性与影响之间的定量关系
DOI：
10.1007/s00493-013-2719-2
复制
发表时间：
2010
期刊：
影响因子：
1.1
通讯作者：
Guy Kindler
中科院分区：
文献类型：
--
作者：
Nathan Keller;Guy Kindler
布尔函数f：{0，1}n → {0，1}被认为是噪声敏感的，如果在其参数中插入一个小的随机错误，使函数的值几乎不可预测。Benjamini，Kalai和Schramm [3]证明了如果f的干扰平方和接近于零，则f一定是噪声敏感的。我们展示了这个结果的一个定量版本，它不依赖于n，并证明了它是紧的某些参数。我们的结果也适用于离散立方体上的一般乘积测度μp，只要log 1/p ≠ logn。我们注意到，在[3]中，也显示了一个定量的关系之间的平方和的inuences和噪声灵敏度，但只有当平方和是有界的n-c为常数c。我们的结果需要推广的Talagrand引理的单调布尔函数的傅立叶系数。为了实现它，我们提出了一个相当短的证明Talagrand引理，很容易推广到各个方向，包括非单调函数。
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.