Summary: The Fourier-Walsh expansion of a Boolean function \(f: \{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’ \(\binom{[n]}{pn} = \{ x \in \{0,1\}^n : \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 : \binom{[n]}{pn} \to \{0,1\}\), the total weight beyond degree \(k\) is at most \(\varepsilon \), where \(\varepsilon =\min(p, 1 - p)^{O(k)} \), then \(f\) can be \(O( \varepsilon )\)-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 \(\varepsilon + \mathrm{exp} (O(k)) \varepsilon^{5/4} \to \varepsilon + \varepsilon^2 (2 \ln (1/ \varepsilon))^k/k!\), which is tight in terms of the dependence on \(\varepsilon\) and misses at most a factor of \(2^{O(k)}\) in the lower-order term.