
arXiv: 1711.09428
We give a structure theorem for Boolean functions on the $p$-biased hypercube which are $\epsilon$-close to degree $d$ in $L_2$, showing that they are close to 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$. We also give an analogous result for monotone Boolean functions on the biased hypercube which are $\epsilon$-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,\epsilon,p$, we identify a class $\mathcal{F}_{d,\epsilon,p}$ of degree $d$ sparse juntas which are $O(\epsilon)$-close to Boolean (in the monotone case, width $d$ sparse DNFs) such that a Boolean function on the $p$-biased hypercube is $O(\epsilon)$-close to degree $d$ in $L_2$ iff it is $O(\epsilon)$-close to a function in $\mathcal{F}_{d,\epsilon,p}$.
FOS: Computer and information sciences, Boolean algebras (Boolean rings), \(p\)-biased distribution, Theory of computing, Computational Complexity (cs.CC), Computer Science - Computational Complexity, sparse functions, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Boolean functions, Miscellaneous topics in information and communication theory, Junta theorem
FOS: Computer and information sciences, Boolean algebras (Boolean rings), \(p\)-biased distribution, Theory of computing, Computational Complexity (cs.CC), Computer Science - Computational Complexity, sparse functions, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Boolean functions, Miscellaneous topics in information and communication theory, Junta theorem
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
