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

Simons Symposium wrapup

For some reason I composed — but forgot to post — the final wrapup post from the Simons Symposium. Even though it’s long since happened, I post it now anyway for posterity…

Continue reading Simons Symposium wrapup