Harmonicity and invariance on slices of the Boolean cube

DOI10.4230/LIPICS.CCC.2016.16MaRDI QIDQ5368750zbMATH OpenOpenAlexFDO

Authors Yuval Filmus, Elchanan Mossel

Publication date 10 October 2017

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

zbMATH Keywords

analysis of Boolean functionsinvariance principleJohnson association schemeslice

Mathematics Subject Classification ID

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

Abstract: In 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 any real-valued function on the slice, whose degree when written as a harmonic multi-linear polynomial is $o(sqrtn)$, has approximately the same distribution under the slice and cube measure. Our proof is based on a novel decomposition of random increasing paths in the cube in terms of martingales and reverse martingales. While such decompositions have been used in the past for stationary reversible Markov chains, ours decomposition is applied in a non-reversible non-stationary setup. We also provide simple proofs for some known and some new properties of harmonic functions which are crucial for the proof. Finally, we provide independent simple proofs for the facts that 1) one cannot distinguish between the slice and the cube based on functions of $o(n)$ coordinates and 2) Boolean symmetric functions on the cube cannot be approximated under the uniform measure by functions whose sum of influences is $o(sqrtn)$.

Recommendations

• Harmonicity and invariance on slices of the Boolean cube
• Invariance principle on the slice
• Invariance principle on the slice
• A structure theorem for almost low-degree functions on the slice
• An orthogonal basis for functions over a slice of the Boolean hypercube

Cited in

(16)

• Boolean degree 1 functions on some classical association schemes
• Weightwise perfectly balanced functions with high weightwise nonlinearity profile
• On non-optimally expanding sets in Grassmann graphs
• Log-Sobolev inequality for the multislice, with applications
• A structure theorem for almost low-degree functions on the slice
• Boolean constant degree functions on the slice are juntas
• Harmonicity and invariance on slices of the Boolean cube
• An orthogonal basis for functions over a slice of the Boolean hypercube
• Combinatorial anti-concentration inequalities, with applications
• Anticoncentration for subgraph statistics
• Invariance principle on the slice
• Vertex isoperimetry and independent set stability for tensor powers of cliques
• Boolean function analysis on high-dimensional expanders
• A log-Sobolev inequality for the multislice, with applications
• Invariance principle on the slice
• Small-set expansion in the Johnson graph

This page was built for publication: Harmonicity and invariance on slices of the Boolean cube

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