Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-180 | 26th November 2017 19:27

Low degree almost Boolean functions are sparse juntas


Authors: Irit Dinur, Yuval Filmus, Prahladh Harsha
Publication: 26th November 2017 20:51
Downloads: 102


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 $\mu_p$ for every *constant* $p$. When $p$ is allowed to be very small, new phenomena emerge. For example, the function $y_1 + \cdots + y_{\epsilon/p}$ (where $y_i \in \{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.

ISSN 1433-8092 | Imprint