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

§11.5: The Berry–Esseen Theorem

Now that we’ve built up some results concerning Gaussian space, we’re motivated to try reducing problems involving Boolean functions to problems involving Gaussian functions. The key tool for this is the Invariance Principle, discussed at the beginning of the chapter. As a warmup, this section is devoted to proving (a form of) the Berry–Esseen Theorem.
Continue reading §11.5: The Berry–Esseen Theorem