Low Influence Functions over Slices of the Boolean Hypercube Depend on Few Coordinates
- Resource Type
- Conference
- Authors
- Wimmer, Karl
- Source
- 2014 IEEE 29th Conference on Computational Complexity (CCC) Computational Complexity (CCC), 2014 IEEE 29th Conference on. :120-131 Jun, 2014
- Subject
- Computing and Processing
Tin
Boolean functions
Shape
Standards
Hypercubes
Vectors
Hamming weight
Boolean function
symmetric group
representation theory
junta theorem
influence
- Language
- ISSN
- 1093-0159
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].