Theory of Computing Library
Graduate Surveys 1
Graduate Surveys 1
A Brief Introduction to Fourier Analysis on the Boolean Cube
Published: September 25, 2008 (20 pages)
Keywords: Fourier analysis, Boolean functions, coding theory, learning theory, hypercontractive inequality, influence of variables, polynomial
Categories: graduate survey, Fourier transform, Fourier analysis, Boolean functions, complexity theory, 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.