Invariance principle on the slice

DOI10.4230/LIPICS.CCC.2016.15zbMATH Open1380.60020arXiv1504.01689MaRDI QIDQ5368749FDOQ5368749

Authors: Yuval Filmus, Guy Kindler, Elchanan Mossel, Karl Wimmer 

Publication date: 10 October 2017

Abstract: We prove an invariance principle for functions on a slice of the Boolean cube, which is the set of all vectors {0,1}^n with Hamming weight k. Our invariance principle shows that a low-degree, low-influence function has similar distributions on the slice, on the entire Boolean cube, and on Gaussian space. Our proof relies on a combination of ideas from analysis and probability, algebra and combinatorics. Our result imply a version of majority is stablest for functions on the slice, a version of Bourgain's tail bound, and a version of the Kindler-Safra theorem. As a corollary of the Kindler-Safra theorem, we prove a stability result of Wilson's theorem for t-intersecting families of sets, improving on a result of Friedgut.

Full work available at URL: https://arxiv.org/abs/1504.01689

Recommendations

• Invariance principle on the slice
• Harmonicity and invariance on slices of the Boolean cube
• Noise stability of functions with low influences: invariance and optimality
• Harmonicity and invariance on slices of the Boolean cube
• A structure theorem for almost low-degree functions on the slice

zbMATH Keywords

invariance principlesliceJohnson association schemeanalysis of Boolean functions

Mathematics Subject Classification ID

Probability measures on topological spaces (60B05) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorial probability (60C05)

Cited In (13)

• Boolean function analysis on high-dimensional expanders
• Combinatorial anti-concentration inequalities, with applications
• Anticoncentration for subgraph statistics
• Harmonicity and invariance on slices of the Boolean cube
• Weightwise perfectly balanced functions with high weightwise nonlinearity profile
• An orthogonal basis for functions over a slice of the Boolean hypercube
• Boolean constant degree functions on the slice are juntas
• Vertex isoperimetry and independent set stability for tensor powers of cliques
• Boolean degree 1 functions on some classical association schemes
• Harmonicity and invariance on slices of the Boolean cube
• On non-optimally expanding sets in Grassmann graphs
• The Okounkov-Vershik approach to the representation theory of \(G\sim S_n\)
• Invariance principle on the slice

This page was built for publication: Invariance principle on the slice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368749)