Invariance Principles in Probability and Their Applications in Theoretical Computer Science

Prahladh Harsha Tata Institute of Fundamental Research School of Technology and Computer Science Homi Bhabha Road
Tuesday, 8 Feb 2011 (all day)
A-212 (STCS Seminar Room)
In recent years, invariance principles in probability (central limit theorem, Berry-Esseen theorem, and their high degree and multi-dimensional generalizations) have come very useful in
theoretical computer science, particularly in the areas of hardness of approximation, derandomization, learning theory, social choice and property testing.

I'll begin this talk by insulting your intelligence by recalling a simple proof of the central limit theorem, with rather weak error bounds using the hybrid argument (aka the Lindeberg method). We will then see how this simple proof can be generalized to yield the high-degree and multi-dimensional versions. Time permitting, I will discuss some of the applications of these generalizations to theoretical computer science.