Abstract
Let f : Z_2^n o {-1,1} be a boolean function. f is in the vector space of functions from Z_2^n into R, which is spanned by the Fourier characters, but the fact that we require f to be boolean imposes restrictions on its Fourier coefficients. It is then natural to consider boolean functions whose Fourier spectrums have some natural property, and try to obtain bounds on their computational complexity in various computational models.
Two such relevant Fourier properties are the number of non-zero Fourier coefficients, known as the sparsity of f, and the spectral norm of f, which is the sum of the absolute values of its Fourier coefficients.
In this talk I will survey several recent results and conjectures regarding the relations between the structure of the Fourier spectrum and complexity theory, in areas such as (parity) decision tree complexity, circuit complexity and communication complexity.