2019/01/25 by Keller, Nathan, Klein, Ohad
#05D40 #05E30 #06E30 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1901.08839
The Fourier-Walsh expansion of a Boolean function f \colon \0,1\n → \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(2k) variables. In this paper we prove a similar theorem for Boolean functions whose domain is the `slice' [n]\choosepn = \x ∈ \0,1\n\colon ∑i xi = pn\, where 0 ≪ p ≪ 1, with respect to their unique representation as harmonic multilinear polynomials. We show that if in the representation of f\colon [n]\choosepn → \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(2k) 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 (2ln(1/ε))k/k!, which is tight in terms of the dependence on ε and misses at most a factor of 2O(k) in the lower-order term.