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.

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

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>