Gaussian noise sensitivity and Fourier tails
Gaussian noise sensitivity and Fourier tails
复制标题
高斯噪声灵敏度和傅里叶尾部
DOI：
10.1109/ccc.2012.35
复制
发表时间：
2012
影响因子：
1
通讯作者：
R. O'Donnell
中科院分区：
文献类型：
--
作者：
Guy Kindler;R. O'Donnell
AbstractWe observe a subadditivity property for the noise sensitivity of subsets of Gaussian space. For subsets of volume 1/2, this leads to an almost trivial proof of Borell’s Isoperimetric Inequality for ρ = cos( π/2ℓ), ℓ ∈ N. Rotational sensitivity also easily gives the Gaussian Isoperimetric Inequality for volume-1/2 sets and a.8787-factor UG-hardness for Max-Cut (within 10−4 of the optimum). As another corollary we show the Hermite tail bound $$||{f^{ > k}}||_2^2 \geqslant \Omega (Var[f]).\frac{1}{{\sqrt k }}for:{R^n} \to \{ - 1,1\} $$||f>k||22≥Ω(Var[f]).1kfor:Rn→{−1,1}. Combining this with the Invariance Principle shows the same Fourier tail bound for any Boolean f: {−1, 1}n → {−1, 1} with all its noisy-influences small, or more strongly, that a Boolean function with tail weight smaller than this bound must be close to a junta. This improves on a result of Bourgain, where the bound on the tail weight was only $$\frac{1}{{{k^{1/2 + o(1)}}}}$$1k1/2+ο(1)
. We also show a simplification of Bourgain’s proof that does not use Invariance and obtains the bound $$\frac{1}{{\sqrt k {{\log }^{1.5}}k}}$$1klog1.5k
.
AbstractWe observe a subadditivity property for the noise sensitivity of subsets of Gaussian space. For subsets of volume 1/2, this leads to an almost trivial proof of Borell’s Isoperimetric Inequality for ρ = cos( π/2ℓ), ℓ ∈ N. Rotational sensitivity also easily gives the Gaussian Isoperimetric Inequality for volume-1/2 sets and a.8787-factor UG-hardness for Max-Cut (within 10−4 of the optimum). As another corollary we show the Hermite tail bound $$||{f^{ > k}}||_2^2 \geqslant \Omega (Var[f]).\frac{1}{{\sqrt k }}for:{R^n} \to \{ - 1,1\} $$||f>k||22≥Ω(Var[f]).1kfor:Rn→{−1,1}. Combining this with the Invariance Principle shows the same Fourier tail bound for any Boolean f: {−1, 1}n → {−1, 1} with all its noisy-influences small, or more strongly, that a Boolean function with tail weight smaller than this bound must be close to a junta. This improves on a result of Bourgain, where the bound on the tail weight was only $$\frac{1}{{{k^{1/2 + o(1)}}}}$$1k1/2+ο(1)
. We also show a simplification of Bourgain’s proof that does not use Invariance and obtains the bound $$\frac{1}{{\sqrt k {{\log }^{1.5}}k}}$$1klog1.5k
.