Chapter 1: Boolean functions and the Fourier expansion

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.

4 comments to Chapter 1: Boolean functions and the Fourier expansion

  • As this page seems to use mathjax, it is worth pointing out that the rendering is improved if certain 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.

  • MathJax script is included using hardcoded `http` scheme, so formulas won’t get rendered if a page is loaded using `https` (modern browsers block insecure scripts).

    You’d better get rid of scheme name altogether by using `src=’//…blabla…’`.

Leave a Reply




You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>