Revision #3 Authors: Irit Dinur, Yuval Filmus, Prahladh Harsha

Accepted on: 26th May 2023 19:46

Downloads: 65

Keywords:

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]

Revision #2 Authors: Irit Dinur, Yuval Filmus, Prahladh Harsha

Accepted on: 26th May 2023 19:42

Downloads: 64

Keywords:

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.

Revision #1 Authors: Irit Dinur, Yuval Filmus, Prahladh Harsha

Accepted on: 26th May 2023 15:33

Downloads: 71

Keywords:

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

TR17-180 Authors: Irit Dinur, Yuval Filmus, Prahladh Harsha

Publication: 26th November 2017 20:51

Downloads: 1448

Keywords:

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.