Low Influence Functions over Slices of the Boolean Hypercube Depend on Few Coordinates
Author:
- Karl WimmerKWKarl Wimmer
- 1 June 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 120-131
Abstract
One of the classic results in analysis of Boolean functions is a result of Friedgut~cite{Fri98} that states that Boolean functions over the hypercube of low influence are approximately juntas, functions which are determined by few coordinates. While this result has also been extended to product distributions, not much is known in the case of nonproduct distributions. We generalize this result to slices of the Boolean cube. A slice of the Boolean cube is the set of strings with some fixed Hamming weight. In this setting, we define the notion of influence and determine a natural orthogonal basis for functions over these domains. We essentially follow the proof for the uniform distribution case, but the set up in order to do so is highly nontrivial. The main techniques used are combinatorics of Young tableaux motivated by the representation theory of the symmetric group along with an application of hypercontractivity in slices of the Boolean hypercube due to O'Donnell and Wimmer OWimmer:[OW09].Keywords
This publication has 15 references indexed in Scilit:
- A structure theorem for Boolean functions with small total influencesAnnals of Mathematics, 2012
- Stability for t-intersecting families of permutationsJournal of Combinatorial Theory, Series A, 2011
- Vertex cover might be hard to approximate to withinJournal of Computer and System Sciences, 2008
- Learning Monotone Decision Trees in Polynomial TimeSIAM Journal on Computing, 2007
- ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUTcomputational complexity, 2006
- A New Approach to the Representation Theory of the Symmetric Groups. IIJournal of Mathematical Sciences, 2005
- On the hardness of approximating vertex coverAnnals of Mathematics, 2005
- Logarithmic Sobolev inequality for some models of random walksThe Annals of Probability, 1998
- On Russo's Approximate Zero-One LawThe Annals of Probability, 1994
- An approximate zero-one lawProbability Theory and Related Fields, 1982