Title: From Smooth Analysis to Circular Law: A Journey via Additive Combinatorics
Speaker: Van Vu, Rutgers University
**Date: Thursday, April 26, 2007 2:00pm - 3:00pm
**Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
**Note special day and location
Abstract:
It was observed many years ago that the eigenvalues of a (non-Hermitian) random matrix seem to distribute uniformly in a circle (circular law). A rigorous explanation was given by Ginibre (1965) for the Gaussian case, and by Bai (1984, following a work of Girko) for general continuous models. The proof for the discrete case is missing.
Another observation in a completely different area: linear programming. It is a very well known phenomenon in the programming community that the simplex method, while proven to be exponential in the worst case, usually runs very fast, beating all other algorithms, even those are proven to be polynomial in all cases. Recently Spielman and Teng came up with a nice explanation (smooth analysis) which relies on the existence of noise in the calculation process. Their analysis assumed continuous noise. The proof for the discrete (and more natural) case is missing.
I will try to fill these missing parts, using tools from additive combinatorics, in particular harmonic analysis.
Joint work with T. Tao, UCLA.