Harmonic analysis and Boolean function complexity (Q1272505)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Harmonic analysis and Boolean function complexity |
scientific article |
Statements
Harmonic analysis and Boolean function complexity (English)
0 references
3 January 1999
0 references
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.
0 references
Fourier transform
0 references
Boolean functions
0 references
Boolean circuit complexity
0 references