Sparse juntas on the biased hypercube

MaRDI QIDQ6507450arXivFDO

Authors Irit Dinur, Yuval Filmus, Prahladh Harsha

Abstract: We give a structure theorem for Boolean functions on the 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(epsilo{n}^{C_d}+p)$-close to constant functions. We pinpoint the exact value of the constant $C_d$.

This page was built for publication: Sparse juntas on the biased hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6507450)