A structure theorem for almost low-degree functions on the slice

Nathan Keller, Ohad Klein

The Fourier-Walsh expansion of a Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is its unique representation as a multilinear polynomial. The Kindler-Safra theorem (2002…