Harmonic analysis and Boolean function complexity
Copyright policy )Harmonic analysis and Boolean function complexity
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.
- Technical University of Munich Germany
- University of Pisa Italy
Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type, Analysis of algorithms and problem complexity, Fourier transform, Numerical methods for trigonometric approximation and interpolation, Boolean functions, Boolean circuit complexity
Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type, Analysis of algorithms and problem complexity, Fourier transform, Numerical methods for trigonometric approximation and interpolation, Boolean functions, Boolean circuit complexity
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).3 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!