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.
[...]


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. [...] 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 [...] 

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