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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references