Chapter 6: Pseudorandomness and ${\mathbb F}_2$-polynomials

In this chapter we discuss various notions of pseudorandomness for boolean functions; by this we mean properties of a fixed boolean function which are in some way characteristic of randomly chosen functions. We will see some deterministic constructions of pseudorandom probability density functions with small support; these have algorithmic application in the field of derandomization. Finally, several of the results in the chapter will involve interplay between the representation of $f : \{0,1\}^n \to \{0,1\}$ as a polynomial over the reals and its representation as a polynomial over ${\mathbb F}_2$.