Invariance Principles in Theoretical Computer Science

Speaker  Ryan O'Donnell

Affiliation  Carnegie Mellon University

Host  Jennifer Chayes

Duration  00:59:37

Date recorded  4 August 2010

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.

©2010 Microsoft Corporation. All rights reserved.
> Invariance Principles in Theoretical Computer Science