Preface xi Prahladh Harsha,Justin Hilyard,Dmitry Itsykson,Hamidreza Jahanjou, Mitchell Johnston,Gautam Kamath,Shiva Kaul,Brian Kell,Pravesh Kothari, Chin Ho Lee,Euiwoong Lee,Holden Lee,Jerry Li,Noam Lifshitz,Tengyu Ma, Mladen Miksa,Aleksandar Nikolov,David Pritchard,Swagato Sanyal,Pranav Senthilnathan,Igor Shinkar,Lior Silberman,Marla Slusky,Dmitry Sokolov, Aravind Srinivasan,Avishay Tal,Li-Yang Tan,Roei Tell,Suresh Venkata- subramanian,Marc Vinyals,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 Matt Franklin and Li-Yang Tan;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 opportu- nities 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 remain- der 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 "Reason- able 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 Copyright Ryan O'Donnell,2014.Preface xi Prahladh Harsha, Justin Hilyard, Dmitry Itsykson, Hamidreza Jahanjou, Mitchell Johnston, Gautam Kamath, Shiva Kaul, Brian Kell, Pravesh Kothari, Chin Ho Lee, Euiwoong Lee, Holden Lee, Jerry Li, Noam Lifshitz, Tengyu Ma, Mladen Mikša, Aleksandar Nikolov, David Pritchard, Swagato Sanyal, Pranav Senthilnathan, Igor Shinkar, Lior Silberman, Marla Slusky, Dmitry Sokolov, Aravind Srinivasan, Avishay Tal, Li-Yang Tan, Roei Tell, Suresh Venkata￾subramanian, Marc Vinyals, 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 Matt Franklin and Li-Yang Tan; extra-special thanks in this group to Noam Lifshitz. I’m grateful to Denis Thérien 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 opportu￾nities 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 remain￾der 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 “Reason￾able 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 Copyright © Ryan O’Donnell, 2014