Low degree almost Boolean functions are sparse juntas
share
Nisan and Szegedy showed that low degree Boolean functions are juntas. Kindler and Safra showed that low degree functions which are almost Boolean are close to juntas. Their result holds with respect to μ_p for every constant p. When p is allowed to be very small, new phenomena emerge. For example, the function y_1 + ... + y_ϵ/p (where y_i ∈{0,1}) is close to Boolean but not close to a junta. We show that low degree functions which are almost Boolean are close to a new class of functions which we call *sparse juntas*. Roughly speaking, these are functions which on a random input look like juntas, in the sense that only a finite number of their monomials are non-zero. This extends a result of the second author for the degree 1 case. As applications of our result, we show that low degree almost Boolean functions must be very biased, and satisfy a large deviation bound. An interesting aspect of our proof is that it relies on a local-to-global agreement theorem. We cover the p-biased hypercube by many smaller dimensional copies of the uniform hypercube, and approximate our function locally via the Kindler--Safra theorem for constant p. We then stitch the local approximations together into one global function that is a sparse junta.
READ FULL TEXT