Contents vii $8.3.Orthogonal decomposition 216 $8.4.p-biased analysis 220 $8.5.Abelian groups 227 $8.6.Highlight:Randomized decision tree complexity 229 $8.7.Exercises and notes 235 Chapter 9.Basics of hypercontractivity 247 $9.1.Low-degree polynomials are reasonable 248 $9.2.Small subsets of the hypercube are noise-sensitive 252 $9.3.(2,g)-and (p,2)-hypercontractivity for a single bit 256 $9.4.Two-function hypercontractivity and induction 259 $9.5.Applications of hypercontractivity 262 $9.6.Highlight:The Kahn-Kalai-Linial Theorem 265 $9.7.Exercises and notes 270 Chapter 10.Advanced hypercontractivity 283 $10.1.The Hypercontractivity Theorem for uniform t1 bits 283 $10.2.Hypercontractivity of general random variables 287 $10.3.Applications of general hypercontractivity 292 §10.4. More on randomization/symmetrization 296 $10.5.Highlight:General sharp threshold theorems 304 $10.6.Exercises and notes 311 Chapter 11.Gaussian space and Invariance Principles 325 $11.1.Gaussian space and the Gaussian noise operator 326 $11.2.Hermite polynomials 334 $11.3.Borell's Isoperimetric Theorem 338 $11.4.Gaussian surface area and Bobkov's Inequality 341 $11.5.The Berry-Esseen Theorem 348 $11.6.The Invariance Principle 355 $11.7.Highlight:Majority Is Stablest Theorem 362 $11.8.Exercises and notes 368 Some tips 387 Bibliography 389 Index 4红1 Revision history 419 Copyright@Ryan O'Donnell,2014.Contents vii §8.3. Orthogonal decomposition 216 §8.4. p-biased analysis 220 §8.5. Abelian groups 227 §8.6. Highlight: Randomized decision tree complexity 229 §8.7. Exercises and notes 235 Chapter 9. Basics of hypercontractivity 247 §9.1. Low-degree polynomials are reasonable 248 §9.2. Small subsets of the hypercube are noise-sensitive 252 §9.3. (2, q)- and (p,2)-hypercontractivity for a single bit 256 §9.4. Two-function hypercontractivity and induction 259 §9.5. Applications of hypercontractivity 262 §9.6. Highlight: The Kahn–Kalai–Linial Theorem 265 §9.7. Exercises and notes 270 Chapter 10. Advanced hypercontractivity 283 §10.1. The Hypercontractivity Theorem for uniform ±1 bits 283 §10.2. Hypercontractivity of general random variables 287 §10.3. Applications of general hypercontractivity 292 §10.4. More on randomization/symmetrization 296 §10.5. Highlight: General sharp threshold theorems 304 §10.6. Exercises and notes 311 Chapter 11. Gaussian space and Invariance Principles 325 §11.1. Gaussian space and the Gaussian noise operator 326 §11.2. Hermite polynomials 334 §11.3. Borell’s Isoperimetric Theorem 338 §11.4. Gaussian surface area and Bobkov’s Inequality 341 §11.5. The Berry–Esseen Theorem 348 §11.6. The Invariance Principle 355 §11.7. Highlight: Majority Is Stablest Theorem 362 §11.8. Exercises and notes 368 Some tips 387 Bibliography 389 Index 411 Revision history 419 Copyright © Ryan O’Donnell, 2014