Spectral Norm of Symmetric Functions

Anil Ada, Omar Fawzi, Hamed Hatami

The spectral norm of a Boolean function $f:\{0,1{\}}^n\to \{-1,1\}$ is the sum of the absolute values of its Fourier coefficients. This quantity provides useful upper and lower boun…