Simple Boolean Functions on the p-biased Hypercube

Nisan and Szegedy showed that low degree Boolean functions are juntas, namely, they depend only on a constant number of their variables. Kindler and Safra showed a robust version of the above: low degree functions which are almost Boolean are close to juntas.

We study the same question on the p-biased hypercube, for very small $p$.  The $p$-biased hypercube is a product probability space in which each coordinate is 1 with probability p and 0 otherwise. In this space most of the measure is on $n$-bit strings whose Hamming weight about $pn \ll n$.

It turns out that here new phenomena emerge. For example, the function $x_1 + ... + x_n=p (where x_i \in {0,1})$ is close to Boolean but not close to a junta.

We characterize low degree functions that are almost Boolean and show that they are close to a new class of functions which we call sparse juntas.

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 (based on joint work with Yuval Filmus and Prahladh Harsha).