The Spectral Norm of Finite Functions

Abstract

In many recent results in learning and computational complexity theory which rely on Fourier analysis, the spectral norm plays a key role. An understanding of this quantity would appear to be useful in both gauging and exploiting these results, and in understanding the underlying techniques.