Filmus, Yuval ;
Mossel, Elchanan
Harmonicity and Invariance on Slices of the Boolean Cube
Abstract
In a recent work with Kindler and Wimmer we proved an invariance principle for the slice for lowinfluence, lowdegree functions. Here we provide an alternative proof for general lowdegree functions, with no constraints on the influences. We show that any realvalued function on the slice, whose degree when written as a harmonic multilinear polynomial is o(sqrt(n)), 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 nonreversible nonstationary 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 known facts that 1) one cannot distinguish between the slice and the cube based on functions of little of of 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(sqrt(n)).
BibTeX  Entry
@InProceedings{filmus_et_al:LIPIcs:2016:5824,
author = {Yuval Filmus and Elchanan Mossel},
title = {{Harmonicity and Invariance on Slices of the Boolean Cube}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {16:116:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5824},
URN = {urn:nbn:de:0030drops58240},
doi = {10.4230/LIPIcs.CCC.2016.16},
annote = {Keywords: analysis of boolean functions, invariance principle, Johnson association scheme, the slice}
}
2016
Keywords: 

analysis of boolean functions, invariance principle, Johnson association scheme, the slice 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

2016 