Ryan O’Donnell: Analysis of Boolean Function

Ryan O’Donnell has begun writing a book about Fourier analysis of Boolean functions and  he serializes it on a blog entiled Analysis of Boolean Function.  New sections appear on Mondays, Wednesdays, and Fridays.

Besides covering the basic theory, Ryan intends to describe applications in theoretical computer science and other areas of mathematics, including combinatorics, probability, social choice, and geometry.

Beside being a great place to learn this interesting material, actively participating in Ryan’s blog can make you a hero! Don’t miss this opportunity.

Each chapter of Ryan’s book ends with a “highlight” illustrating the use of Boolean analysis in problems where you might not necessarily expect it. In a post over Computational Complexity Ryan described some of these highlights in order to give a flavor of the contents:

• 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)