Harmonic analysis and Boolean function complexity

Abstract:

Any attempt to find connections between mathematical properties of functions and their computational complexity has strong relevance to theory of computation. Indeed, there is the hope that developing new mathematical techniques could lead to discovering properties that might be responsible for lower bounds. The current situation is that none of the known techniques has yet led to lower bounds in general models of computation.

The subject of this paper is related to the above general arguments. More precisely, we study the Fourier Transform of Boolean functions, and analyze the extent to which mathematical techniques from the area of abstract harmonic analysis can provide some insight in our current understanding of Boolean circuit complexity. In addition to presenting new applications of Fourier analysis to circuit complexity, we give the necessary background on abstract harmonic analysis and review some work on the subject.