Yuval Filmus
Abstract
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.
- Rudolf Ahlswede and Levon H. Khachatrian. 1997. The complete intersection theorem for systems of finite sets. Eur. J. Comb. 18, 2 (1997), 125--136 Google Scholar
Digital Library
- Rudolf Ahlswede and Levon H. Khachatrian. 1998. The diametric theorem in hamming spaces—Optimal anticodes. Adv. Appl. Math. 20, 4 (1998), 429--449. Google ScholarDigital Library
- Rudolf Ahlswede and Levon H. Khachatrian. 1999. A pushing-pulling method: New proofs of intersection theorems. Combinatorica 19, 1 (1999), 1--15.Google ScholarCross Ref
- Eiichi Bannai and Tatsuro Ito. 1984. Algebraic Combinatorics I: Association Schemes. Benjamin/Cummings Pub. Co.Google Scholar
- C. Borell. 1985. Geometric bounds on the Ornstein--Uhlenbeck velocity process. Z. Wahrsch. Verw. Gebiete 70, 1 (1985), 1--13.Google ScholarCross Ref
- Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar. 2015. Direct sum testing. In ITCS 2015. Google ScholarDigital Library
- Anindya De, Elchanan Mossel, and Joe Neeman. 2013. Majority is stablest: Discrete and SoS. In 45th ACM Symposium on Theory of Computing. 477--486. Google ScholarDigital Library
- Irit Dinur and Shmuel Safra. 2005. On the hardness of approximating minimum vertex cover. Ann. Math. 162, 1 (2005), 439--485.Google ScholarCross Ref
- Charles F. Dunkl. 1976. A Krawtchouk polynomial addition theorem and wreath products of symmetric groups. Indiana Univ. Math. J. 25 (1976), 335--358.Google ScholarCross Ref
- Charles F. Dunkl. 1979. Orthogonal functions on some permutation groups. In Relations Between Combinatorics and Other Parts of Mathematics (Proc. Symp. Pure Math.), Vol. 34. Amer. Math. Soc., Providence, RI, 129--147.Google ScholarCross Ref
- David Ellis, Nathan Keller, and Noam Lifshitz. 2016. Stability for the complete intersection theorem, and the forbidden intersection problem of Erdős and Sós. arXiv:1604.06135.Google Scholar
- David Ellis, Nathan Keller, and Noam Lifshitz. 2016. Stability versions of Erdős--Ko--Rado type theorems, via Isoperimetry. arXiv:1604.02160.Google Scholar
- Paul Erdős, Chao Ko, and Richard Rado. 1961. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford 12, 2 (1961), 313--320.Google ScholarCross Ref
- Yuval Filmus. 2013. Spectral Methods in Extremal Combinatorics. Ph.D. dissertation. University of Toronto.Google Scholar
- Yuval Filmus. 2016. An orthogonal basis for functions over a slice of the boolean hypercube. Elec. J. Comb. 23, 1 (2016), P1.23.Google Scholar
- Yuval Filmus and Ferdinand Ihringer. 2018. Boolean constant degree functions on the slice are juntas. CoRR abs/1801.06338 (2018). arxiv:1801.06338 http://arxiv.org/abs/1801.06338Google Scholar
- Péter Frankl. 1987. Erdős-Ko-Rado theorem with conditions on the maximal degree. J. Comb. Theory A 46 (1987), 252--263. Google ScholarDigital Library
- Peter Frankl, Sang June Lee, Mark Siggers, and Norihide Tokushige. 2014. An Erdős--Ko--Rado theorem for cross--intersecting families. J. Combin. Th., Ser. A 128 (2014), 207--249. Google ScholarDigital Library
- Peter Frankl and Norihide Tokushige. 1992. Some best-possible inequalities concerning cross-intersecting families. J. Combin. Th., Ser. A 61 (1992), 87--97. Google ScholarDigital Library
- Ehud Friedgut. 2008. On the measure of intersecting families, uniqueness and stability. Combinatorica 28, 5 (2008), 503--528. Google ScholarDigital Library
- Marcus Isaksson and Elchanan Mossel. 2012. Maximally stable Gaussian partitions with discrete applications. Israel J. Math. 189, 1 (2012), 347--396.Google ScholarCross Ref
- Nathan Keller and Ohad Klein. 2017. Kindler--Safra theorem for the slice. In Preparation.Google Scholar
- Subhash Khot. 2010. Inapproximability of NP-complete problems, discrete Fourier analysis, and geometry. In Proceedings of the International Congress of Mathematicians.Google Scholar
- Guy Kindler. 2002. Property Testing, PCP and Juntas. Ph.D. dissertation. Tel-Aviv University.Google Scholar
- Guy Kindler, Naomi Kirshner, and Ryan O’Donnell. 2014. Gaussian noise sensitivity and Fourier tails. http://www.cs.cmu.edu/∼odonnell/papers/gaussian-noise-sensitivity.pdf.Google Scholar
- Guy Kindler and Shmuel Safra. 2004. Noise-resistant Boolean functions are juntas. Unpublished manuscript.Google Scholar
- Tzong-Yau Lee and Horng-Tzer Yau. 1998. Logarithmic Sobolev inequality for some models of random walks. Ann. Prob. 26, 4 (1998), 1855--1873.Google Scholar
- László Lovász. 1979. On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25 (1979), 1--7. Google ScholarDigital Library
- Elchanan Mossel and Yuval Filmus. 2016. Harmonicity and invariance on slices of the Boolean cube. In 31st Conference on Computational Complexity. Google ScholarDigital Library
- Elchanan Mossel and Yuval Filmus. 2017. Harmonicity and Invariance on Slices of the Boolean Cube. Submitted.Google Scholar
- Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz. 2010. Noise stability of functions with low influences: Invariance and optimality. Ann. Math. 171 (2010), 295--341.Google ScholarCross Ref
- Noam Nisan and Mario Szegedy. 1994. On the degree of Boolean functions as real polynomials. Comput. Complexity 4, 4 (1994), 301--313. Google ScholarDigital Library
- Ryan O’Donnell. 2014. Analysis of Boolean Functions. Cambridge University Press. Google ScholarDigital Library
- Li Qiu and Xingzhi Zhan. 2007. On the span of Hadamard products of vectors. Linear Algebra Appl. 422 (2007), 304--307.Google ScholarCross Ref
- Murali K. Srinivasan. 2011. Symmetric chains, Gelfand--Tsetlin chains, and the Terwilliger algebra of the binary Hamming scheme. J. Algebr. Comb. 34, 2 (2011), 301--322. Google ScholarDigital Library
- Hajime Tanaka. 2009. A note on the span of Hadamard products of vectors. Linear Algebra Appl. 430 (2009), 865--867.Google ScholarCross Ref
- Richard M. Wilson. 1984. The exact bound in the Erdős-Ko-Rado theorem. Combinatorica 4 (1984), 247--257.Google ScholarCross Ref
- Karl Wimmer. 2014. Low influence functions over slices of the Boolean hypercube depend on few coordinates. In CCC. Google ScholarDigital Library
Index Terms
- Invariance Principle on the Slice
Recommendations
Invariance principle on the slice
CCC '16: Proceedings of the 31st Conference on Computational ComplexityThe 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 f(B1, ..., Bn) is close (in various senses) to the ...
Harmonicity and invariance on slices of the boolean cube
CCC '16: Proceedings of the 31st Conference on Computational ComplexityIn a recent work with Kindler and Wimmer we proved an invariance principle for the slice for low-influence, low-degree functions. Here we provide an alternative proof for general low-degree functions, with no constraints on the influences. We show that ...
Boolean constant degree functions on the slice are juntas
AbstractWe show that a Boolean degree d function on the “slice” [ n ] k ≜ { ( x 1 , … , x n ) ∈ { 0 , 1 } : ∑ i = 1 n x i = k } is a junta (depends on a constant number γ ( d ) of coordinates), assuming that k , n − k are large enough. This ...
Comments