ECCC-Report TR17-180https://eccc.weizmann.ac.il/report/2017/180Comments and Revisions published for TR17-180en-usSun, 26 Nov 2017 20:51:22 +0200
Paper TR17-180
| Low degree almost Boolean functions are sparse juntas |
Yuval Filmus,
Irit Dinur,
Prahladh Harsha
https://eccc.weizmann.ac.il/report/2017/180 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.Sun, 26 Nov 2017 20:51:22 +0200https://eccc.weizmann.ac.il/report/2017/180