Boolean Functions with Small Approximate Spectral Norm

Tsun-Ming Cheung, Hamed Hatami, Rosie Zhao +1

The sum of the absolute values of the Fourier coefficients of a function $f:{\mathbb{F}}_2^n\to \mathbb{R}$ is called the spectral norm of $f$. Green and Sanders' quantitative versi…