In this chapter we describe the basics of analysis of boolean functions. We emphasize viewing the Fourier expansion of a boolean function as its representation as a real multilinear polynomial. The viewpoint based on harmonic analysis over ${\mathbb F}_2^n$ is mostly deferred to Chapter 3. We illustrate the use of basic Fourier formulas through the analysis of the Blum–Luby–Rubinfeld linearity test.
|
||||||
Chapter 1: Boolean functions and the Fourier expansion2 comments to Chapter 1: Boolean functions and the Fourier expansionLeave a Reply |
||||||
|
Copyright © 2013 Ryan O'Donnell -- All Rights Reserved |
||||||
As this page seems to use mathjax, it is worth pointing out that the rendering is improved if certain fonts ( http://www.mathjax.org/help/fonts/ ) are installed. These fonts also allow better rendering when printing.
Thanks Michael. I should also point out that (at least on my machine) pages take an unusually long time to render in IE. Chrome seems to be the fastest option. I wish I didn’t have to suggest “Use a different browser” if people find it slow, but unfortunately I’m committed to MathJax at this point.