A structure theorem for almost low-degree functions on the slice
Preprint
Abstract
The Fourier-Walsh expansion of a Boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ is its unique representation as a multilinear polynomial. The Kindler-Safra theorem (2002) asserts that if in the expansion of $f$, the total weight on coefficients beyond degree $k$ is very small, then $f$ can be approximated by a Boolean-valued function depending on at most $O(2^k)$ variables. In this paper we prove a similar theorem for Boolean functions whose domain is the `slice' ${{[n]}\choose{pn}} = \{x \in \{0,1\}^n\colon \sum_i x_i = pn\}$, where $0 \ll p \ll 1$, with respect to their unique representation as harmonic multilinear polynomials. We show that if in the representation of $f\colon {{[n]}\choose{pn}} \rightarrow \{0,1\}$, the total weight beyond degree $k$ is at most $\epsilon$, where $\epsilon = \min(p, 1-p)^{O(k)}$, then $f$ can be $O(\epsilon)$-approximated by a degree-$k$ Boolean function on the slice, which in turn depends on $O(2^{k})$ coordinates. This proves a conjecture of Filmus, Kindler, Mossel, and Wimmer (2015). Our proof relies on hypercontractivity, along with a novel kind of a shifting procedure. In addition, we show that the approximation rate in the Kindler-Safra theorem can be improved from $\epsilon + \exp(O(k)) \epsilon^{1/4}$ to $\epsilon+\epsilon^2 (2\ln(1/\epsilon))^k/k!$, which is tight in terms of the dependence on $\epsilon$ and misses at most a factor of $2^{O(k)}$ in the lower-order term.
Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean functionCombinatorica, 2020
- Boolean constant degree functions on the slice are juntasDiscrete Mathematics, 2019
- Invitation to intersection problems for finite setsJournal of Combinatorial Theory, Series A, 2016
- Between arrow and Gibbard-Satterthwaite; A representation theoretic approachIsrael Journal of Mathematics, 2014
- Symmetric chains, Gelfand–Tsetlin chains, and the Terwilliger algebra of the binary Hamming schemeJournal of Algebraic Combinatorics, 2011
- On the measure of intersecting families, uniqueness and stabilityCombinatorica, 2008
- Graph Products, Fourier Analysis and Spectral TechniquesGeometric and Functional Analysis, 2004
- Boolean Functions With Low Average Sensitivity Depend On Few CoordinatesCombinatorica, 1998
- The Complete Intersection Theorem for Systems of Finite SetsEuropean Journal of Combinatorics, 1997
- The influence of variables in product spacesIsrael Journal of Mathematics, 1992