The Condition Number of a Random Matrix: From von Neumann-Goldstine to Spielman-Teng

Van Vu
Rutgers, The State University of New Jersey
September 27, 2010

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 ?

Super-uniformity of the typical billiard path (proof included)

Jozsef Beck
Institute for Advanced Study
October 4, 2010

I will describe the proof of the following surprising result: the typical billiard paths form the family of the most uniformly distributed curves in the unit square. I will justify this vague claim with a precise statement. As a byproduct, we obtain the counter-intuitive fact that the complexity of the test set is almost irrelevant. The error term is shockingly small, and it does not matter that we test uniformity with a nice set (like a circle or a square), or with an arbitrarily ugly Lebesgue measurable subset of the unit square.