Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Invariance Principle on the Slice

Invariance Principle on the Slice 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Invariance Principle on the Slice

Download PDF
37 pages

Loading next page...
 
/lp/association-for-computing-machinery/invariance-principle-on-the-slice-e00XDbcMnq
Publisher
Association for Computing Machinery
Copyright
Copyright © 2018 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3186590
Publisher site
See Article on Publisher Site

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.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Apr 13, 2018

Keywords: Analysis of Boolean functions

References

  • The complete intersection theorem for systems of finite sets
    Ahlswede, Rudolf; Khachatrian, Levon H.
  • The diametric theorem in hamming spaces—Optimal anticodes
    Ahlswede, Rudolf; Khachatrian, Levon H.
  • A pushing-pulling method: New proofs of intersection theorems
    Ahlswede, Rudolf; Khachatrian, Levon H.
  • Algebraic Combinatorics I: Association Schemes
    Bannai, Eiichi; Ito, Tatsuro
  • Geometric bounds on the Ornstein--Uhlenbeck velocity process
    Borell, C.
  • Direct sum testing
    David, Roee; Dinur, Irit; Goldenberg, Elazar; Kindler, Guy; Shinkar, Igor
  • Majority is stablest: Discrete and SoS
    De, Anindya; Mossel, Elchanan; Neeman, Joe
  • On the hardness of approximating minimum vertex cover
    Dinur, Irit; Safra, Shmuel
  • A Krawtchouk polynomial addition theorem and wreath products of symmetric groups
    Dunkl, Charles F.
  • Orthogonal functions on some permutation groups
    Dunkl, Charles F.
  • Stability for the complete intersection theorem, and the forbidden intersection problem of Erdős and Sós
    Ellis, David; Keller, Nathan; Lifshitz, Noam
  • Stability versions of Erdős--Ko--Rado type theorems, via Isoperimetry
    Ellis, David; Keller, Nathan; Lifshitz, Noam
  • Intersection theorems for systems of finite sets
    Erdős, Paul; Ko, Chao; Rado, Richard
  • Spectral Methods in Extremal Combinatorics
    Filmus, Yuval
  • An orthogonal basis for functions over a slice of the boolean hypercube
    Filmus, Yuval
  • Boolean constant degree functions on the slice are juntas
    Filmus, Yuval; Ihringer, Ferdinand
  • Erdős-Ko-Rado theorem with conditions on the maximal degree
    Frankl, Péter
  • An Erdős--Ko--Rado theorem for cross--intersecting families
    Frankl, Peter; Lee, Sang June; Siggers, Mark; Tokushige, Norihide
  • Some best-possible inequalities concerning cross-intersecting families
    Frankl, Peter; Tokushige, Norihide
  • On the measure of intersecting families, uniqueness and stability
    Friedgut, Ehud
  • Maximally stable Gaussian partitions with discrete applications
    Isaksson, Marcus; Mossel, Elchanan
  • Kindler--Safra theorem for the slice
    Keller, Nathan; Klein, Ohad
  • Inapproximability of NP-complete problems, discrete Fourier analysis, and geometry
    Khot, Subhash
  • Property Testing, PCP and Juntas
    Kindler, Guy
  • Gaussian noise sensitivity and Fourier tails
    Kindler, Guy; Kirshner, Naomi; O’Donnell, Ryan
  • Noise-resistant Boolean functions are juntas
    Kindler, Guy; Safra, Shmuel
  • Logarithmic Sobolev inequality for some models of random walks
    Lee, Tzong-Yau; Yau, Horng-Tzer
  • On the Shannon capacity of a graph
    Lovász, László
  • Harmonicity and invariance on slices of the Boolean cube
    Mossel, Elchanan; Filmus, Yuval
  • Harmonicity and Invariance on Slices of the Boolean Cube
    Mossel, Elchanan; Filmus, Yuval
  • Noise stability of functions with low influences: Invariance and optimality
    Mossel, Elchanan; O’Donnell, Ryan; Oleszkiewicz, Krzysztof
  • On the degree of Boolean functions as real polynomials
    Nisan, Noam; Szegedy, Mario
  • Analysis of Boolean Functions
    O’Donnell, Ryan
  • On the span of Hadamard products of vectors
    Qiu, Li; Zhan, Xingzhi
  • Symmetric chains, Gelfand--Tsetlin chains, and the Terwilliger algebra of the binary Hamming scheme
    Srinivasan, Murali K.
  • A note on the span of Hadamard products of vectors
    Tanaka, Hajime
  • The exact bound in the Erdős-Ko-Rado theorem
    Wilson, Richard M.
  • Low influence functions over slices of the Boolean hypercube depend on few coordinates
    Wimmer, Karl