Boolean functions are perhaps the most basic objects of study in theoretical computer science. They also arise in other areas of mathematics, including combinatorics, statistical physics, and mathematical social choice. The field of analysis of Boolean functions seeks to understand them via their Fourier transform and other analytic methods. This text gives a thorough overview of the field, beginning with the most basic definitions and proceeding to advanced topics such as hypercontractivity and is operimetry. Each chapter includes a "highlight application" such as Arrow's theorem from economics, the Goldreich-Levin algorithm from cryptography/learning theory, Hastad's NP-hardness ˚ of approximation results, and "sharp threshold" theorems for random graph properties. The book includes nearly 500 exercises and can be used as the basis of a one-semester graduate course. It should appeal to advanced undergraduates, graduate students, and researchers in computer science theory and related mathematical fields.

The subject of this textbook is the analysis of Boolean functions. Roughly speaking, this refers to studying Boolean functions f : {0, 1}n → {0, 1} via their Fourier expansion and other analytic means. Boolean functions are perhaps the most basic object of study in theoretical computer science, and Fourier analysis has become an indispensable tool in the field. The topic has also played a key role in several other areas of mathematics, from combinatorics, random graph theory, and statistical physics, to Gaussian geometry, metric/Banach spaces, and social choice theory.
The intent of this book is both to develop the foundations of the field and to give a wide (though far from exhaustive) overview of its applications. Each chapter ends with a "highlight" showing the power of analysis of Boolean functions in different subject areas: property testing, social choice, cryptography, circuit complexity, learning theory, pseudorandomness, hardness of approximation, concrete complexity, and random graph theory.
The book can be used as a reference for working researchers or as the basis of a one-semester graduate-level course. The author has twice taught such a course at Carnegie Mellon University, attended mainly by graduate students in computer science and mathematics but also by advanced undergraduates, postdocs, and researchers in adjacent fields. In both years most of Chapters 1–5 and 7 were covered, along with parts of Chapters 6, 8, 9, and 11, and some additional material on additive combinatorics. Nearly 500 exercises are provided at the ends of the book's chapters.
Additional material related to the book can be found at its website:
http://analysisofbooleanfunctions.org
This includes complete lecture notes from the author's 2007 course, complete lecture videos from the author's 2012 course, blog updates related to analysis of Boolean functions, an electronic draft of the book, and errata. The author would like to encourage readers to post any typos, bugs, clarification requests, and suggestions to this website.
Acknowledgments
My foremost acknowledgment is to all of the people who have taught me analysis of Boolean functions, especially Guy Kindler and Elchanan Mossel. I also learned a tremendous amount from my advisor Madhu Sudan, and my coauthors and colleagues Per Austrin, Eric Blais, Nader Bshouty, Ilias Diakonikolas, Irit Dinur, Uri Feige, Ehud Friedgut, Parikshit Gopalan, Venkat Guruswami, Johan Hastad, Gil Kalai, Daniel Kane, Subhash Khot, Adam Klivans, James Lee, ˚ Assaf Naor, Joe Neeman, Krzysztof Oleszkiewicz, Yuval Peres, Oded Regev, Mike Saks, Oded Schramm, Rocco Servedio, Amir Shpilka, Jeff Steif, Benny Sudakov, Li-Yang Tan, Avi Wigderson, Karl Wimmer, John Wright, Yi Wu, Yuan Zhou, and many others. Ideas from all of them have strongly informed this book.
Many thanks to my PhD students who suffered from my inattention during the completion of this book: Eric Blais, Yuan Zhou, John Wright, and David Witmer. I'd also like to thank the students who took my 2007 and 2012 courses on analysis of Boolean functions; special thanks to Deepak Bal, Carol Wang, and Patrick Xia for their very helpful course writing projects.
Thanks to my editor Lauren Cowles for her patience and encouragement, to the copyediting team of David Anderson and Rishi Gupta, and to Cambridge University Press for welcoming the free online publication of this book. Thanks also to Amanda Williams for the use of the cover image on the book's website.
I'm very grateful to all of the readers of the blog serialization who suggested improvements and pointed out mistakes in the original draft of this work: Amirali Abdullah, Stefan Alders, anon, Arda Antikacıoglu, Albert Atserias, ˘ Deepak Bal, Paul Beame, Tim Black, Ravi Boppana, Sankardeep Chakraborty, Bireswar Das, Andrew Drucker, John Engbers, Diodato Ferraioli, Magnus Find, Michael Forbes, David Garc´ıa Soriano, Dmitry Gavinsky, Daniele Gewurz, Sivakanth Gopi, Tom Gur, Zachary Hamaker, Prahladh Harsha, Justin Hilyard, Dmitry Itsykson, Hamidreza Jahanjou, Mitchell Johnston, Gautum Kamath, Shiva Kaul, Brian Kell, Pravesh Kothari, Chin Ho Lee, Euiwoong Lee, Noam Lifshitz, Tengyu Ma, Aleksandar Nikolov, David Pritchard, Swagato Sanyal, Pranav Senthilnathan, Igor Shinkar, Lior Silberman, Marla Slusky, Avishay Tal, Li-Yang Tan, Roei Tell, Suresh Venkatasubramanian, Emanuele Viola, Poorvi Vora, Amos Waterland, Karl Wimmer, Chung Hoi Wong, Xi Wu, Yi Wu, Mingji Xia, Yuichi Yoshida, Shengyu Zhang, and Yu Zhao. Special thanks in this group to Albert Atserias, Dima Gavinsky, and Tim Black; extraspecial thanks in this group to Li-Yang Tan; super-extra-special thanks in this group to Noam Lifshitz.
I'm grateful to Denis Therien for inviting me to lecture at the Barbados ´ Complexity Workshop, to Cynthia Dwork and the STOC 2008 PC for inviting me to give a tutorial, and to the Simons Foundation who arranged for me to co-organize a symposium together with Elchanan Mossel and Krzysztof Oleskiewicz, all on the topic of analysis of Boolean functions. These opportunities greatly helped me to crystallize my thoughts on the topic.
I worked on this book while visiting the Institute for Advanced Study in 2010–2011 (supported by the Von Neumann Fellowship and in part by NSF grants DMS-0835373 and CCF-0832797); I'm very grateful to them for having me and for the wonderful working environment they provided. The remainder of the work on this book was done at Carnegie Mellon; I'm of course very thankful to my colleagues there and to the Department of Computer Science. "Reasonable" random variables were named after the department's "Reasonable Person Principle." I was also supported in this book-writing endeavor by the National Science Foundation, specifically grants CCF-0747250 and CCF-1116594. As usual: "This material is based upon work supported by the National Science Foundation under grant numbers listed above. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation (NSF)."
Finally, I'd like to thank all of my colleagues, friends, and relatives who encouraged me to write and to finish the book, Zeynep most of all.
Ryan O'Donnell
Pittsburgh
October 2013

Preface page xi

List of Notation xv

1. Boolean Functions and the Fourier Expansion 1

1.1. On Analysis of Boolean Functions 1

1.2. The "Fourier Expansion": Functions as Multilinear Polynomials 2

1.3. The Orthonormal Basis of Parity Functions 5

1.4. Basic Fourier Formulas 7

1.5. Probability Densities and Convolution 12

1.6. Highlight: Almost Linear Functions and the BLR Test 14

1.7. Exercises and Notes 17

2. Basic Concepts and Social Choice 26

2.1. Social Choice Functions 26

2.2. Influences and Derivatives 29

2.3. Total Influence 32

2.4. Noise Stability 36

2.5. Highlight: Arrow's Theorem 41

2.6. Exercises and Notes 45

3. Spectral Structure and Learning 54

3.1. Low-Degree Spectral Concentration 54

3.2. Subspaces and Decision Trees 56

3.3. Restrictions 59

3.4. Learning Theory 64

3.5. Highlight: The Goldreich-Levin Algorithm 68

3.6. Exercises and Notes 71

4. DNF Formulas and Small-Depth Circuits 79

4.1. DNF Formulas 79

4.2. Tribes 82

4.3. Random Restrictions 84

4.4. Hastad's Switching Lemma and the Spectrum of DNFs 86

4.5. Highlight: LMN's Work on Constant-Depth Circuits 89

4.6. Exercises and Notes 94

5. Majority and Threshold Functions 99

5.1. Linear Threshold Functions and Polynomial Threshold Functions 99

5.2. Majority, and the Central Limit Theorem 104

5.3. The Fourier Coefficients of Majority 108

5.4. Degree-1 Weight 111

5.5. Highlight: Peres's Theorem and Uniform Noise Stability 118

5.6. Exercises and Notes 122

6. Pseudorandomness and F2-Polynomials 131

6.1. Notions of Pseudorandomness 131

6.2. F2-Polynomials 136

6.3. Constructions of Various Pseudorandom Functions 140

6.4. Applications in Learning and Testing 144

6.5. Highlight: Fooling F2-Polynomials 149

6.6. Exercises and Notes 153

7. Property Testing, PCPPs, and CSPs 162

7.1. Dictator Testing 162

7.2. Probabilistically Checkable Proofs of Proximity 167

7.3. CSPs and Computational Complexity 173

7.4. Highlight: Hastad's Hardness Theorems ˚ 180

7.5. Exercises and Notes 186

8. Generalized Domains 197

8.1. Fourier Bases for Product Spaces 197

8.2. Generalized Fourier Formulas 201

8.3. Orthogonal Decomposition 207

8.4. p-Biased Analysis 211

8.5. Abelian Groups 218

8.6. Highlight: Randomized Decision Tree Complexity 222

8.7. Exercises and Notes 228

9. Basics of Hypercontractivity 240

9.1. Low-Degree Polynomials Are Reasonable 241

9.2. Small Subsets of the Hypercube Are Noise-Sensitive 246

9.3. (2, q)- and (p, 2)-Hypercontractivity for a Single Bit 250

9.4. Two-Function Hypercontractivity and Induction 254

9.5. Applications of Hypercontractivity 256

9.6. Highlight: The Kahn–Kalai–Linial Theorem 260

9.7. Exercises and Notes 266

10. Advanced Hypercontractivity 278

10.1. The Hypercontractivity Theorem for Uniform ±1 Bits 278

10.2. Hypercontractivity of General Random Variables 283

10.3. Applications of General Hypercontractivity 288

10.4. More on Randomization/Symmetrization 293

10.5. Highlight: General Sharp Threshold Theorems 301

10.6. Exercises and Notes 310

11. Gaussian Space and Invariance Principles 325

11.1. Gaussian Space and the Gaussian Noise Operator 326

11.2. Hermite Polynomials 335

11.3. Borell's Isoperimetric Theorem 339

11.4. Gaussian Surface Area and Bobkov's Inequality 343

11.5. The Berry–Esseen Theorem 350

11.6. The Invariance Principle 359

11.7. Highlight: Majority Is Stablest Theorem 366

11.8. Exercises and Notes 373

Some Tips 393

Bibliography 395

Index 417

ryan o'donnell is an Associate Professor in the Computer Science Department at Carnegie Mellon University.

中科院文献情报中心