On the Structure of Boolean Functions with Small Spectral Norm

Amir Shpilka, Avishay Tal, Ben lee Volk

In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of f is $\Vert \hat{f}{\Vert }_1={\sum }_{\alpha }|\hat{f}(\alpha )|$). Specifically, we prove the follo…