Yuval Filmus: Structure of Boolean Almost Low Degree Functions on the Biased Cube

The FKN theorem states that if a Boolean function on the Boolean cube is close to degree 1, then it is close to a dictator. Similarly, the Kindler-Safra theorem states that if a Boolean function on the Boolean cube is close to degree d, then it is close to a junta.

The picture becomes more interesting when we study functions on the p-biased Boolean cube. If a Boolean function is 𝜀-close to degree 1, then (up to negation) it is O(𝜀)-close to a maximum of O(√𝜀/p+1) coordinates, and so O(√𝜀+p)-close to a constant function. A similar statement holds for functions close to degree d, but the corresponding structure is more complicated.Another setting we might discuss is functions on the symmetric group. If a Boolean function is 𝜀-close to degree 1, then it is O(√𝜀)-close to a dictator (suitably defined), and O(𝜀)-close (up to negation) to a union of ‘mostly disjoint’ cosets. A similar statement should hold for degree d, where the function ought to be close to a (suitably defined) decision tree of depth poly(d).

Joint work with Irit Dinur (Weizmann Institute) and Prahladh Harsha (TIFR). This talk relates to this arXiv paper.

This video was produced by the Simons Institute, and forms part of the workshop Structural Results.