DLS - Ryan O'Donnell, "Wake Up Babe, New Probability Just Dropped"

Abstract:
Do you love probability?  But are you sad that all the good stuff was done 100+ years ago?  Like, you'll never get to be Boole (1847) inventing the Union Bound, or Chebyshev (1867) inventing Chebyshev's Inequality, or Markov (1906) inventing Markov Chains?  

Well, good news!  Turns out that what you think of as The Laws Of Probability is just a subset of the *actual* laws that govern how random things happen in our universe.  So Boole and Chebyshev and Markov were just doing special cases; the *real* Union Bound and Chebyshev Inequality and theory of Markov Chains were worked out just over the last couple of decades.  I'll tell you about it, and maybe you can be the first to work out the general version of *your* favorite probability result.

(PS: this talk is about quantum computing.)

Based on joint works with: Ramgopal Venkateswaran; Robin Kothari; and, Scott Aaronson, Mohammad Bavarian, Toby Cubitt, Sabee Grewal, Giulio Gueltrini, and Marien Raat.

Bio: 
Ryan O'Donnell is a Canadian theoretical computer scientist and a professor at Carnegie Mellon University. He is known for his work on the analysis of Boolean functions and for authoring the textbook on this subject. He is also known for his work on computational learning theory, hardness of approximation, property testing, quantum computation and quantum information.

O'Donnell completed his B.Sc. in Mathematics and Computer Science at the University of Toronto. He then completed his Ph.D. at the Massachusetts Institute of Technology (MIT) in 2003, advised by Madhu Sudan.