Continue reading Chapter 11 exercises, continued
Continue reading Chapter 11 exercises


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 MaxCut CSP. 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$.) 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. 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 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 GeneralVolume Majority Is Stablest Theorem); in particular, it’s the special case arising from the limit $\rho \to 1^{}$. [Editor's note  just a reminder that these daily updates are almost entirely thanks to LiYang 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. 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). 

Copyright © 2018 Ryan O'Donnell  All Rights Reserved 
Recent comments