Analysis of Boolean Functions blog/book (Guest post by Ryan O'Donnell)

(Guest post by Ryan O'Donnell)

Lance and Bill have graciously let me plug my recently begun book/blog project, analysis of boolean functions. I am writing a textbook on analysis of Boolean functions and serializing it on the blog as I go. When I'm done, the book will be available online; hopefully it will also be published in the conventional format. (NOTE FROM BILL- its also linked to off of our blog page.)

The topic is sometimes called Boolean Fourier analysis, though my perspective is a bit more from probability theory than harmonic analysis. I hope the book will be accessible and of interest to grad students and researchers in theoretical computer science and other areas of mathematics. Each chapter will end with a "highlight" illustrating the use of Boolean analysis in problems where you might not necessarily expect it. To give you a flavor of the contents, my planned list of highlights is:

• Testing linearity (the Blum-Luby-Rubinfeld Theorem)
• Arrow's Theorem from Social Choice (and Kalai's "approximate" version)
• The Goldreich-Levin Algorithm from cryptography
• Constant-depth circuits (Linial-Mansour-Nisan's work)
• Noise sensitivity of threshold functions (Peres's Theorem)
• Pseudorandomness for F_2-polynomials (Viola's Theorem)
• NP-hardness of approximately solving linear systems (Hastad's Theorem)
• Randomized query complexity of monotone graph properties
• The (almost-)Polynomial Freiman-Ruzsa Theorem (i.e., Sanders's Theorem)
• The Kahn-Kalai-Linial Theorem on influences
• The Gaussian Isoperimetric Inequality (Bobkov's proof)
• Sharp threshold phenomena (Friedgut and Bourgain's theorems)
• Majority Is Stablest Theorem
• Unique Games-hardness from SDP gaps (work of Raghavendra and others)

If you're interested, you can think of it like an online course -- I've been publishing Mondays, Wednesdays, and Fridays, and there are even exercises. (Also like a course, I'll go on break for a few weeks around the new year.) Come see why "juntas" are important, what hypercontractivity "really" means, and why functions on Gaussian space are the "easy special case" of Boolean functions...

PS: I'm using MathJax for the posts; if anyone has suggestions for me or for readers on how to make it look nicer or load better, please do let me know.