Abstract
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).