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)
This entry was posted in Combinatorics, Computer Science and Optimization and tagged , , . Bookmark the permalink.

One Response to Ryan O’Donnell: Analysis of Boolean Function

  1. Pingback: Mathblogging.org Weekly Picks « Mathblogging.org — the Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s