Invariance Principle on the Slice
Invariance Principle on the Slice
复制标题
切片不变性原理
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
K. Wimmer
中科院分区：
文献类型：
--
作者：
Yuval Filmus;Guy Kindler;Elchanan Mossel;K. Wimmer
Mossel、奥唐纳和Oleszkiewicz的非线性不变性原理确定，如果f（x1，...，xn）是具有低影响的多线性低次多项式，则如果f（b1，.，bn）接近（在各种意义上）的分布f（G1，..，Gn），其中Bi ∈R {-1，1}是独立的Bernoulli随机变量，Gi <$N（0，1）是独立的标准高斯型.不变性原理在理论计算机科学中有许多应用，包括多数是最稳定的猜想，它表明MAX-CUT的Goemans-Williamson算法在唯一博弈猜想下是最优的。更一般地说，MOO的不变性原理适用于任何两个超压缩随机变量向量（X1，...，Xn），（Y1，...，Yn），使得（i）匹配矩：Xi和Yi具有匹配的一阶矩和二阶矩;（ii）独立性：变量X1，...，Xn是独立的，Y1，...，Yn也是独立的。独立性条件对于定理的证明是至关重要的，然而在某些情况下，我们希望使用分布X1，.，Xn，其中各个坐标不是独立的。一个常见的例子是片（[n]k）上的均匀分布，片（[n]k）由所有具有汉明权重k的向量（x1，.，xn）∈{0，1}n组成。这一切片出现在理论计算机科学（硬度放大、直和测试）、极值组合学（埃尔德什-柯-拉多定理）和编码理论（以约翰逊关联方案为幌子）中。我们的主要结果是一个不变原理，其中（X1，...，Xn）是切片（[n]pn）上的均匀分布，（Y1，...，Yn）由n个独立的Ber（p）随机变量或n个独立的N（p，p（1-p））随机变量组成.作为应用程序，我们证明了一个版本的多数是稳定的功能片，版本的布尔甘的尾巴定理，版本的Kindler-Safra结构定理，和一个稳定的版本的t-相交Erdens-Ko-Rado定理，结合技术的威尔逊和Friedgut。我们的证明依赖于分析和概率，代数和组合学的思想组合。特别是，我们必须利用最近的工作的第一作者，它描述了一个明确的傅立叶基切片。
The non-linear invariance principle of Mossel, O’Donnell, and Oleszkiewicz establishes that if f(x1,… ,xn) is a multilinear low-degree polynomial with low influences, then the distribution of if f(b1,…,bn) is close (in various senses) to the distribution of f(G1,…,Gn), where Bi ∈R {-1,1} are independent Bernoulli random variables and Gi ∼ N(0,1) are independent standard Gaussians. The invariance principle has seen many applications in theoretical computer science, including the Majority is Stablest conjecture, which shows that the Goemans–Williamson algorithm for MAX-CUT is optimal under the Unique Games Conjecture. More generally, MOO’s invariance principle works for any two vectors of hypercontractive random variables (X1,… ,Xn),(Y1,… ,Yn) such that (i) Matching moments: Xi and Yi have matching first and second moments and (ii) Independence: the variables X1,… ,Xn are independent, as are Y1,…,Yn. The independence condition is crucial to the proof of the theorem, yet in some cases we would like to use distributions X1,… ,Xn in which the individual coordinates are not independent. A common example is the uniform distribution on the slice ([n]k) which consists of all vectors (x1,…,xn)∈{0,1}n with Hamming weight k. The slice shows up in theoretical computer science (hardness amplification, direct sum testing), extremal combinatorics (Erdős–Ko–Rado theorems), and coding theory (in the guise of the Johnson association scheme). Our main result is an invariance principle in which (X1,…,Xn) is the uniform distribution on a slice ([n]pn and (Y1,… ,Yn) consists either of n independent Ber(p) random variables, or of n independent N(p,p(1-p)) random variables. As applications, we prove a version of Majority is Stablest for functions on the slice, a version of Bourgain’s tail theorem, a version of the Kindler–Safra structural theorem, and a stability version of the t-intersecting Erdős–Ko–Rado theorem, combining techniques of Wilson and Friedgut. Our proof relies on a combination of ideas from analysis and probability, algebra, and combinatorics. In particular, we make essential use of recent work of the first author which describes an explicit Fourier basis for the slice.