Invariance Principles in Theoretical Computer Science


August 4, 2010


Ryan O'Donnell


Carnegie Mellon University


In this talk I will give proofs of some “invariance principles” in probability; the Central Limit Theorem, the Berry–Esseen Theorem, and multidimensional and higher-degree versions thereof. I will discuss these proofs from a computer science perspective, and show some applications to fields such as property testing, derandomization, learning, and inapproximability.


Ryan O'Donnell

Ryan O’Donnell received a B. Sc. from the University of Toronto in 1999 and a Ph.D. from the MIT Mathematics Department in 2003. His Ph.D. advisor was Madhu Sudan. Following this he was a postdoc at IAS for a year in Avi Wigderson’s group, and a postdoc at Microsoft Research for two years in Jennifer Chayes’s group. Since 2006 he has been an assistant professor in the Computer Science Department at Carnegie Mellon University. Ryan’s research interests include Analysis of Boolean Functions, Hardness of Approximation, Learning Theory, and Probability.