Harmonic analysis and Boolean function complexity

DOI10.1007/S100920050014MaRDI QIDQ1272505zbMATH OpenOpenAlexFDO

Authors K. Appert, Aldo Bernasconi

Publication date 3 January 1999

Published in Calcolo (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s100920050014

zbMATH Keywords

Boolean circuit complexityBoolean functionsFourier transform

Mathematics Subject Classification ID

Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Numerical methods for trigonometric approximation and interpolation (65T40) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• Analysis of Boolean Functions
• On the distribution of the Fourier spectrum of Boolean functions
• On the complexity of balanced Boolean functions

Cited in

(16)

• Approximate location of relevant variables under the crossover distribution.
• Boolean functions: influence, threshold and noise
• On the distribution of the Fourier spectrum of Boolean functions
• Using the renormalization group to classify Boolean functions
• On spectral techniques in analysis of Boolean networks
• Computability in harmonic analysis
• A geometrical representation of the Fourier transformation of Boolean functions
• On a hierarchy of Boolean functions hard to compute in constant depth
• Minimal polynomial of Cayley graph adjacency matrix for Boolean functions
• Boolean nested canalizing functions: a comprehensive analysis
• Analysis of Boolean Functions
• On the Walsh-Fourier analysis of Boolean functions
• Learning intersections and thresholds of halfspaces
• Asymptotic insights for projection, Gordon-Lewis, and Sidon constants in Boolean cube function spaces
• Noise stability of functions with low influences: invariance and optimality
• On the Fourier spectrum of symmetric Boolean functions

This page was built for publication: Harmonic analysis and Boolean function complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1272505)