






















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 $ε$, where $ε= \min(p, 1-p)^{O(k)}$, then $f$ can be $O(ε)$-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 $ε+ \exp(O(k)) ε^{1/4}$ to $ε+ε^2 (2\ln(1/ε))^k/k!$, which is tight in terms of the dependence on $ε$ and misses at most a factor of $2^{O(k)}$ in the lower-order term.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。