Lectures on YouTube

Not sure why I didn’t do this earlier, but I put onto YouTube the 23 lectures on Analysis of Boolean Functions from 2012.

In case you’re interested, I put some additional collections of filmed lectures there, including:

28 lectures on Undergraduate Computational Complexity, from 2017;

26 lectures (incomplete) from the 1st-year course “Great Ideas in Theoretical Computer Science”.

My two-lecture intro to Analysis of Boolean Functions, at St. Petersburg State University


Now analysisofbooleanfunctions.net

After forgetting to renew the .org domain too many times, I gave up and got a new one. The .org address is now deprecated, and the correct link is now http://analysisofbooleanfunctions.net

Analysis of Boolean Functions book now available for free download

I’m happy to say that I’ve finally gotten things set up so that you can download a PDF of the book. The official web address for this is http://get.analysisofbooleanfunctions.net, or you can click “DOWNLOAD THE PDF” on the blog’s main page.

A small warning: On the download page, I am using a “Google form” to ask for your email address, to which the PDF will be sent. I promise not to send you any other emails; just the one containing the attached PDF. I would also like to warn that I think Google allows at most 100 emails per day, so there is some small chance that we might hit the limit today. If that happens, please try again tomorrow! Finally, the server hosting this website has been a bit flaky lately; I hope it will be fine in the future.

Many thanks to Cambridge University Press for agreeing (several years ago!) to allow the PDF to be freely available. Of course, I’m also very thankful to the heroes who sent in comments and bug-fixes to the blog draft of the book. Please feel free to continue doing so — I’m happy to keep making corrections.

Regarding the differences between the printed book and the electronic version: The printed book is “Version 1.00″ and the PDF is “Version 1.01″. The main difference is that about 40 small typos/bugs have been fixed (nothing major; in almost all cases you can easily guess the correct thing once you notice the mistake). I would also like to add that the numbering of the theorems/definitions/exercises/etc. is identical between the printed book and the PDF, so if you would like to cite something, it doesn’t matter which version you cite. The page numbering is not the same, though, so please try not to cite things by page number.

Once more, thanks again to all the readers of the blog; I hope you enjoy the book!

Added later: We hit 100 emails; however, it appears that the downloads are still working. But in any case, if you have trouble, please try again tomorrow.

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