Sparse juntas on the biased hypercube

We give a structure theorem for Boolean functions on the p-biased hypercube which are -close to degree d in L₂, showing that they are close to sparse juntas. Our structure theorem implies that such functions are O (^Cd + p) -close to constant functions. We pinpoint the exact value of the constant Cd. We also give an analogous result for monotone Boolean functions on the biased hypercube which are -close to degree d in L₂, showing that they are close to sparse DNFs. Our structure theorems are optimal in the following sense: for every d, , p, we identify a class F₃, , ₏ of degree d sparse juntas which are O () -close to Boolean (in the monotone case, width d sparse DNFs) such that a Boolean function on the p-biased hypercube is O () -close to degree d in L₂ iff it is O () -close to a function in F₃, , ₏.