The video for Lecture 5 of the online course is available on the course web page.
|
||||||
|
In this section we describe some applications of our study of pseudorandomness. The video for Lecture 4 of the online course is available on the course web page. The video for Lecture 3 of the online course is available on the course web page. In this section we give some constructions of boolean functions with strong pseudorandomness properties. The video for Lecture 2 of the online course is available on the course web page. 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. 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. 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). 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$. |
||||||
|
Copyright © 2013 Ryan O'Donnell -- All Rights Reserved |
||||||
Recent comments