Harmonic analysis and Boolean function complexity (Q1272505)

The author studies the Fourier transform of Boolean functions and analyzes the extent to which mathematical techniques from abstract harmonic analysis can provide some insight in the current understanding of Boolean circuit complexity. The main part of the paper systematically studies properties of the Fourier analysis on hypercubes with the aim of gaining new insights for the analysis of Boolean functions. The second part reviews known results relating the Fourier spectrum of Boolean functions to their size complexity and presents new applications of Fourier analysis to circuit complexity.