We give a structure theorem for Boolean functions on the biased hypercube which are $\varepsilon$-close to degree~$d$ in $L_2$, showing that they are close to \emph{sparse juntas}.
Our structure theorem implies that such functions are $O(\varepsilon^{C_d}+p)$-close to constant functions. We pinpoint the exact value of the constant $C_d$.

Significant Changes since Version v1 (starting from title). In particular (1) the theorem statements are considerably stronger (2) a monotone version of the main theorem is added and (3) the proof uses a weaker agreement theorem compared to the earlier version.
[Please ignore revisions 1 and 2]

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.

Significant Changes since Version v1 (starting from title). In particular (1) the theorem statements are considerably stronger (2) a monotone version of the main theorem is added and (3) the proof uses a weaker agreement theorem compared to the earlier version.

We give a structure theorem for Boolean functions on the biased hypercube which are $\epsilon$-close to degree~$d$ in $L_2$, showing that they are close to \emph{sparse juntas}.
Our structure theorem implies that such functions are $O(\epsilon^{C_d} + p)$-close to constant functions. We pinpoint the exact value of the constant $C_d$.

Considerably revised previous version. In particular, (1) proof uses a weaker version of the agreement theorem and (2) monotone version

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.