Theory of Computing Library
Graduate Surveys 1

A Brief Introduction to Fourier Analysis on the Boolean Cube

by Ronald de Wolf

Published: September 25, 2008    (20 pages)
DOI: 10.4086/toc.gs.2008.001

Download article from ToC site:
[PS (358K)]    [PS.GZ (110K)]    [PS.ZIP (110K)]
[PDF (292K)]    [DVI (182K)]    [TeX (46K)]
Misc.:
[HTML Bibliography] [Bibliography Source] [BibTeX] 
[About the Author(s)]
Keywords: Fourier analysis, Boolean functions, coding theory, learning theory, hypercontractive inequality, influence of variables, polynomial
Categories: graduate survey, Fourier transform, Fourier analysis, Boolean functions, learning, influence, error-correcting codes
ACM Classification: F.0, F.2
AMS Classification: 42-02, 68-02, 68Q17, 68Q25, 68Q32

Abstract: [Plain Text Version]

We give a brief introduction to the basic notions of Fourier analysis on the Boolean cube, illustrated and motivated by a number of applications in theoretical computer science.