Simons Symposium 2014 — Day 1

Li-Yang here.

Avi Wigderson kicked off this year’s symposium with a talk describing recent joint work with Dimitri Gavinsky, Or Meir, and Omri Weinstein attacking one of the central open problems in computational complexity: does ${\mathsf P} = \mathsf{NC}^1$, or in words, can every sequential computation be efficiently parallelized?
Continue reading Simons Symposium 2014 — Day 1

Simons Symposium 2014 — Discrete Analysis: Beyond the Boolean Cube

I’m pleased to announce that this week we’ll be reporting on the 2014 Simons Symposium — Discrete Analysis: Beyond the Boolean Cube. This is the second of three biannual symposia on Analysis of Boolean Functions, sponsored by the Simons Foundation. You may remember our reports on the 2012 edition which took place in Caneel Bay, US Virgin Islands. This year we’re lucky to be holding the symposium in Rio Grande, Puerto Rico.

The Beach

Room with a view

I’m also happy to report that we will have guest blogging by symposium attendee Li-Yang Tan. This year’s talk lineup looks quite diverse, with topics ranging from the Bernoulli Conjecture Theorem to Fourier analysis on the symmetric group, to additive number theory. Stay tuned!

§11.3: Borell’s Isoperimetric Theorem

If we believe that the Majority Is Stablest Theorem should be true, then we also have to believe in its “Gaussian special case”. Let’s see what this Gaussian special case is.
Continue reading §11.3: Borell’s Isoperimetric Theorem

§11.2: Hermite polynomials

Having defined the basic operators of importance for functions on Gaussian space, it’s useful to also develop the analogue of the Fourier expansion.
Continue reading §11.2: Hermite polynomials

§11.1: Gaussian space and the Gaussian noise operator

We begin with a few definitions concerning Gaussian space.
Continue reading §11.1: Gaussian space and the Gaussian noise operator

The book is available for pre-order

I’m happy to announce that the book is very nearly completed. In fact, you can pre-order a copy now, either directly from Cambridge University Press, or from Amazon (currently with a 10% discount). If all goes well, the book will become physically available at the end of May. Fairly soon thereafter I will also make a pdf “final draft” version freely available here at the website.

In the meantime, I will continue to serialize the final chapter (Chapter 11) as usual over the next month. In fact, I had to trim and glue together the planned Chapters 11 and 12. Also, as mentioned earlier, I dropped a chapter on Additive Combinatorics that would have gone between Chapters 8 and 9, although its “highlight”, Sanders’s Theorem, is here on the blog. Oh well, I had to wrap this project up at some point; at least you’ll have an idea of what will be in the 2nd Edition. :)

Chapter 11: Gaussian space and Invariance Principles

The final destination of this chapter is a proof of the following theorem due to Mossel, O’Donnell, and Oleszkiewicz [MOO05a,MOO10], first mentioned in Chapter 5.25:

Majority Is Stablest Theorem Fix $\rho \in (0,1)$. Let $f : \{-1,1\}^n \to [-1,1]$ have $\mathop{\bf E}[f] = 0$. Then, assuming $\mathbf{MaxInf}[f] \leq \epsilon$, or more generally that $f$ has no $(\epsilon,\epsilon)$-notable coordinates, \[ \mathbf{Stab}_\rho[f] \leq 1 – \tfrac{2}{\pi} \arccos \rho + o_\epsilon(1). \]

Continue reading Chapter 11: Gaussian space and Invariance Principles

Chapter 10 notes

Continue reading Chapter 10 notes

Chapter 10 exercises

Continue reading Chapter 10 exercises

§10.5: Highlight: General sharp threshold theorems

In Chapter 8.4 we described the problem of “threshold phenomena” for monotone functions $f : \{-1,1\}^n \to \{-1,1\}$.
Continue reading §10.5: Highlight: General sharp threshold theorems