Tata Institute of Fundamental Research
Invariance Principles in Probability and Their Applications in Theoretical Computer Science
Colloquium
Speaker:
Prahladh Harsha
Tata Institute of Fundamental Research
School of Technology and Computer Science
Homi Bhabha Road
Date:
Tuesday, 8 Feb 2011 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Prahladh Harsha Tata Institute of Fundamental Research School of Technology and Computer Science Homi Bhabha Road |
| Date: | Tuesday, 8 Feb 2011 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.
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.