abstract
Video of this lecture| COMPUTER SCIENCE AND DISCRETE MATHEMATICS II | |
| Topic: | Invariance Principles in Theoretical Computer Science |
| Speaker: | Ryan O'Donnell |
| Affiliation: | Carnegie Mellon University; Member, School of Mathematics |
| Date: | Tuesday, September 21 |
| Time/Room: | 10:30am - 12:30pm/S-101 |
| Video Link: | https://video.ias.edu/csdm/odonnell |
In this talk I will insult your intelligence by showing a non-original proof of the Central Limit Theorem, with not-particularly-good error bounds. However, the proof is very simple and flexible, allowing generalizations to multidimensional and higher-degree invariance principles. Time permitting, I will also discuss applications to areas of theoretical computer science: property testing, derandomization, learning, and inapproximability.