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.