## CMU online course: Lecture 5 published

The video for Lecture 5 of the online course is available on the course web page.

## §6.4: Applications in learning and testing

In this section we describe some applications of our study of pseudorandomness.
Continue reading §6.4: Applications in learning and testing

## CMU Online Course: Lecture 4 posted

The video for Lecture 4 of the online course is available on the course web page.

## CMU Online Course: Lecture 3 posted

The video for Lecture 3 of the online course is available on the course web page.

## §6.3: Constructions of various pseudorandom functions

In this section we give some constructions of boolean functions with strong pseudorandomness properties.
Continue reading §6.3: Constructions of various pseudorandom functions

## CMU Online Course: Lecture 2 posted

The video for Lecture 2 of the online course is available on the course web page.

## CMU online course

This fall I am teaching a graduate class on Analysis of Boolean Functions at Carnegie Mellon, crosslisted in the computer science and math departments. I’m happy to announce that it will also be available ‘online’ to a limited extent. The lectures will be made available as videos, the course bulletin board is open to the public for discussions, and the problem sets will be available. Regarding the homework, I’m happy to take LaTeX solutions (as described here) and to discuss the problems on the bulletin board, but I’ll only be grading the homework of the actual CMU students.

The videos, problem sets, and instructions on how to access the bulletin board are all on the course webpage. Look for a new video each Monday and Wednesday and a new section of the book here on the blog each Friday.

## §6.2: ${\mathbb F}_2$-polynomials

We began our study of boolean functions in Chapter 1.2 by considering their polynomial representations over the real field. In this section we take a brief look at their polynomial representations over the field ${\mathbb F}_2$, with $\mathsf{False}$, $\mathsf{True}$ being represented by $0, 1 \in {\mathbb F}_2$ as usual. Note that in the field ${\mathbb F}_2$, the arithmetic operations $+$ and $\cdot$ correspond to logical XOR and logical AND, respectively.
Continue reading §6.2: ${\mathbb F}_2$-polynomials

## §6.1: Notions of pseudorandomness

The most obvious spectral property of a truly random function $\boldsymbol{f} : \{-1,1\}^n \to \{-1,1\}$ is that all of its Fourier coefficients are very small (as we saw in Exercise 5.8).
Continue reading §6.1: Notions of pseudorandomness

## 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$.