Sparse juntas on the biased hypercube
Open Access
- 30 July 2024
- journal article
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 3
Abstract
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}$.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Agreement Tests on Graphs and HypergraphsSIAM Journal on Computing, 2025
- Pseudorandom sets in Grassmann graph have near-perfect expansionAnnals of Mathematics, 2023
- Junta Threshold for Low Degree Boolean Functions on the SliceThe Electronic Journal of Combinatorics, 2023
- A structure theorem for almost low-degree functions on the sliceIsrael Journal of Mathematics, 2020
- An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean functionCombinatorica, 2020
- Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests: [Extended abstract]2019
- New Direct-Product Testers and 2-Query PCPsSIAM Journal on Computing, 2012
- Boolean functions whose Fourier transform is concentrated on the first two levelsAdvances in Applied Mathematics, 2002
- Polynomials with two valuesCombinatorica, 1997
- On the degree of boolean functions as real polynomialscomputational complexity, 1994