Sparse juntas on the biased hypercube

arXiv1711.09428MaRDI QIDQ6507450FDOQ6507450

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)