§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…

§11.4: Gaussian surface area and Bobkov’s Inequality

This section is devoted to studying the Gaussian Isoperimetric Inequality. This inequality is a special case of the Borell Isoperimetric Inequality (and hence also a special case of the General-Volume Majority Is Stablest Theorem); in particular, it’s the special case arising from the limit $\rho \to 1^{-}$.
Continue reading §11.4: Gaussian surface area and Bobkov’s Inequality

Simons Symposium 2014 — Day 4

[Editor's note -- just a reminder that these daily updates are almost entirely thanks to Li-Yang Tan.]

The first speaker of the day was Sergey Bobkov, who spoke about concentration on the cube and its relationship with various isoperimetric problems, including highlights of his own work.
Continue reading Simons Symposium 2014 — Day 4

Simons Symposium 2014 — Day 3

The first speaker of the day was Subhash Khot, who discussed his recent work with Madhur Tulsiani and Pratik Worah giving a complete characterization of the approximation resistance of constraint satisfaction problems (CSPs) under Subhash’s Unique Games Conjecture (UGC).
Continue reading Simons Symposium 2014 — Day 3

Simons Symposium 2014 — Day 2

The second day began with Tom Sanders speaking about the Bourgain-Green sumset problem in additive combinatorics, including some of his own work on the problem.
Continue reading Simons Symposium 2014 — Day 2

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.

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