Low degree almost Boolean functions are sparse juntas
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Analysis of Boolean Functions2014
- Direct Product Testing2014
- Locally Testing Direct Product in the Low Error Range2008
- On the distribution of the fourier spectrum of Boolean functionsIsrael Journal of Mathematics, 2002
- Boolean functions whose Fourier transform is concentrated on the first two levelsAdvances in Applied Mathematics, 2002
- Sharp thresholds of graph properties, and the $k$-sat problemJournal of the American Mathematical Society, 1999
- Boolean Functions With Low Average Sensitivity Depend On Few CoordinatesCombinatorica, 1998
- Every monotone graph property has a sharp thresholdProceedings of the American Mathematical Society, 1996
- On the degree of boolean functions as real polynomialscomputational complexity, 1994
- The influence of variables on Boolean functions1988