Fourier Analysis of boolean functions basics, with applications to voting
Sep 30, 2009
Abstract: This is the first in a two-part talk on the basics of
Fourier analysis of boolean functions. In this talk, I'll explain the
Fourier expansion and how it relates to properties of boolean
functions such as "influences" and "noise sensitivity". I will give
motivations from the theory of voting, and conclude by giving a
Fourier-theoretic proof of Arrow's Impossibility Theorem.