Fall 2013

Structure of the Fourier Spectrum of Boolean Functions and Complexity

Monday, Dec. 2, 2013 10:45 am11:30 am PST

Add to Calendar

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.