Nesin Mathematics Village and Swedish Summer School

Within the last two months I had the privilege of teaching a week-long Analysis of Boolean Functions course at two different summer schools.

In July I was at the (First Annual?) Swedish Summer School in Computer Science. This was wonderfully organized by KTH faculty Per Austrin, Johan Håstad, and Jakob Nordström, and took place on the scenic island of Djurhamn in the Stockholm archipelago. Boaz Barak and I alternated lectures (he on Sums of Squares) to 50 or so highly motivated graduate students. I was very impressed that many of them worked quite hard on the homework outside of lecture times! Some photos by Talya Abram can be found here, including one of me holding an exquisite table linen gift, with the De–Mossel–Neeman differential equation in the background.

The second summer school (just finished) was held at the Nesin Mathematical Village, an idyllic site in the hills near the Aegean coast of Turkey. The village operates year-round, but its main business is in the summer, when a hundred or so high school, college, and graduate math students come each week for courses. The spirit of the place is charming, and the math village itself is quite beautiful, as you can see from these photos. I lectured here, though I wish I got to lecture here.

By the way, if you ever teach a class on Analysis of Boolean Functions yourself, please drop me a line; I like to keep track of links to them. (So far I know of 31 such courses since 2002.)

ICM 2014

I’m currently in Seoul for the 2014 ICM, where I’ll be giving a talk on — what else? — analysis of Boolean functions. I’ve written an accompanying article for the proceedings, Social choice, computational complexity, Gaussian geometry, and Boolean functions, the abstract of which follows:

We describe a web of connections between the following topics: the mathematical theory of voting and social choice; the computational complexity of the Maximum Cut problem; the Gaussian Isoperimetric Inequality and Borell’s generalization thereof; the Hypercontractive Inequality of Bonami; and, the analysis of Boolean functions. A major theme is the technique of reducing inequalities about Gaussian functions to inequalities about Boolean functions $f : \{-1,1\}^n \to \{-1,1\}$, and then using induction on $n$ to further reduce to inequalities about functions $f : \{-1,1\} \to \{-1,1\}$. We especially highlight De, Mossel, and Neeman’s recent use of this technique to prove the Majority Is Stablest Theorem and Borell’s Isoperimetric Inequality simultaneously.

The article actually includes a few ideas that don’t explicitly appear in the book, so please take a look if you’re interested. I hope the article will make a nice fit for the congress; it has a few connections (some major, some minor) with work being discussed by several other speakers here, including Boaz Barak, Andrei Bulatov, Sourav Chatterjee, Julia Chuzhoy, Alessio Figalli, Monique Laurent, Michel Ledoux, and (last but certainly not least) our newest Nevanlinna Prize winner, Subhash Khot. (Congratulations Subhash!) Indeed, my talk on Saturday will mostly center around a very famous conjecture made by Subhash — I refer, of course, to the Majority Is Stablest Conjecture. :)

PS: In case you happen to actually be at the congress, you can buy a “special ICM edition” of the book for $30 (or, even cheaper, ₩30,000) at the Cambridge University Press booth.

Typos and mistakes

Another big thank-you to all the heroes who have found, and who continue to find, typos and mistakes in the book! Please keep them coming!

One small note: In the relatively near future I will post here an electronic version of the book. It will actually be version 1.01, with version 1.00 being the printed book. The electronic version will include fixes for typos found subsequent to the book’s printing.

Due to laziness, however, I will stop incorporating fixes into the old blog posts. So those are now basically deprecated. Feel free to take a look at them till the PDF comes out, of course. But this means there’s a chance that when you find a typo or mistake on the blog pages, I might respond with “Thanks — someone else found that too, and it’s already been corrected.”

Once again, thanks so much to all of you for the corrections!

The blog is finished, the book is available

The last post concluded the serialization of the book. Cambridge University Press has also just finished the full print run. You can peruse a physical copy of the book if you happen to go to STOC (look for the Cambridge table staffed by Lauren Cowles). The book will be shipping from, e.g., Amazon starting some time next week.

There will be at least one more post on this blog; I will release a free PDF of the book in its entirety some time around September. Watch this space!

Some tips

  • You might try using analysis of Boolean functions whenever you’re faced with a problems involving Boolean strings in which both the uniform probability distribution and the Hamming graph structure play a role. More generally, the tools may still apply when studying functions on (or subsets of) product probability spaces.
  • If you’re mainly interested in unbiased functions, or subsets of volume $\frac12$, use the representation $f : \{-1,1\}^n \to \{-1,1\}$. If you’re mainly interested in subsets of small volume, use the representation $f : \{-1,1\}^n \to \{0,1\}$.
  • As for the domain, if you’re interested in the operation of adding two strings (modulo $2$), use $\mathbb{F}_2^n$. Otherwise use $\{-1,1\}^n$.
  • If you have a conjecture about Boolean functions:
    • Test it on dictators, majority, parity, tribes (and maybe recursive majority of $3$). If it’s true for these functions, it’s probably true.
    • Try to prove it by induction on $n$.
    • Try to prove it in the special case of functions on Gaussian space.
  • Try not to prove any bound on Boolean functions $f : \{-1,1\}^n \to \{-1,1\}$ that involves the parameter $n$.
  • Analytically, the only multivariate polynomials we really know how to control are degree-$1$ polynomials. Try to reduce to this case if you can.
  • Hypercontractivity is useful in two ways: (i) It lets you show that low-degree functions of independent random variables behave “reasonably”. (ii) It implies that the noisy hypercube graph is a small-set expander.
  • Almost any result about functions on the hypercube extends to the case of the $p$-biased cube, and more generally, to the case of functions on products of discrete probability spaces in which every outcome has probability at least $p$ — possibly with a dependence on $p$, though.
  • Every Boolean function consists of a junta part and Gaussian part.

Chapter 11 notes

The subject of Gaussian space is too enormous to be surveyed here; some recommended texts include Janson [Jan97] and Bogachev [Bog98], the latter having an extremely thorough bibliography.
Continue reading Chapter 11 notes

Chapter 11 exercises, continued

Continue reading Chapter 11 exercises, continued

Chapter 11 exercises

Continue reading Chapter 11 exercises

§11.7: Highlight: Majority Is Stablest Theorem

The Majority Is Stablest Theorem (to be proved at the end of this section) was originally conjectured in 2004 [KKMO04,KKMO07]. The motivation came from studying the approximability of the Max-Cut CSP.
Continue reading §11.7: Highlight: Majority Is Stablest Theorem

§11.6: The Invariance Principle

Let’s summarize the Variant Berry–Esseen Theorem and proof from the preceding section, using slightly different notation. (Specifically, we’ll rewrite $\boldsymbol{X}_i = a_i {\boldsymbol{x}}_i$ where $\mathop{\bf Var}[{\boldsymbol{x}}_i] = 1$, so $a_i = \pm \sigma_i$.)
Continue reading §11.6: The Invariance Principle