Title: A structure theorem for almost low-degree functions on the slice,
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.