(Introduction to the Lecture Series and and overview for those unable to attend the whole Lecture Series)
The condition number of a matrix is at the heart of numerical linear algebra. In the 1940s von-Neumann and Goldstine, motivated by the problem of inverting, posed the following question:
(1) What is the condition number of a random matrix ?
During the years, this question was raised again and again, by various researchers (Smale, Demmel etc). About ten years ago, motivated by "Smoothed Analysis", Spielman and Teng raised a more general question:
(2) What is the condition number of a randomly perturbed matrix ?
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.