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$. Some announcements: First, the book serialization will start back up again on Monday; stay tuned. Second, 22 videos from the Simons Symposium are now available. Third, there will be a special issue of Theory of Computing devoted to analysis of Boolean functions (see below announcement); please submit your good papers! The journal Theory of Computing is soliciting papers for a special issue dedicated to the Analysis of Boolean Functions. This topic plays a crucial role in the theory of computing and has significant applications to other areas of mathematics, to statistical physics, and to economics. In the past decade, several important themes have emerged in the analysis of Boolean functions, including the dichotomy between “juntas” and “low-influence” functions, noise stability and sensitivity, Gaussian analysis, probabilistic invariance principles, small-set expansion, and regularity lemmas. Progress in the field has led to several breakthrough applications over the last few years, in areas such as inapproximability, communication complexity, threshold phenomena, extremal combinatorics, and percolation theory. The idea of this special issue was conceived at the Simons Symposium “Analysis of Boolean Functions“ held at Caneel Bay, US Virgin Islands, February 5-11, 2012. This workshop joins a number of recent workshops bringing together researchers in the area (1, 2, 3, 4, 5, 6). Further activity is planned for fall 2013 when the Simons Institute will devote a special semester to Real Analysis in Computer Science.
Please indicate your intention to submit a paper for this special issue in advance in an email to special issue editor Ryan O’Donnell, odon… [at] cs.cmu.edu. To submit a paper for the special issue, please follow the
Elchanan Mossel and Ryan O’Donnell
Oded Regev This blog will go on hiatus for the summer (except for responding to comments). See you in September. Chow’s Theorem was proved by independently by Chow [Cho61] and by Tannenbaum [Tan61] in 1961; see also [Elg61]. |
||||||
|
Copyright © 2013 Ryan O'Donnell -- All Rights Reserved |
||||||
Recent comments