Sparse juntas on the biased hypercube

Abstract

We give a structure theorem for Boolean functions on the $p$-biased hypercube which are $\hat{I}\mu$-close to degree $d$ in $L_2$, showing that they are close to sparse juntas. Our structure theorem implies that such functions are $O(\hat{I}{\mu }^{C_d}+p)$-close to constant functions. We pinpoint the exact value of the constant $C_d$. We also give an analogous result for monotone Boolean functions on the biased hypercube which are $\hat{I}\mu$-close to degree $d$ in $L_2$, showing that they are close to sparse DNFs. Our structure theorems are optimal in the following sense: for every $d,\hat{I}\mu ,p$, we identify a class ${\mathcal{F}}_{d,\hat{I}\mu ,p}$ of degree $d$ sparse juntas which are $O(\hat{I}\mu )$-close to Boolean (in the monotone case, width $d$ sparse DNFs) such that a Boolean function on the $p$-biased hypercube is $O(\hat{I}\mu )$-close to degree $d$ in $L_2$ iff it is $O(\hat{I}\mu )$-close to a function in ${\mathcal{F}}_{d,\hat{I}\mu ,p}$.

44 pages. TheoretiCS journal article