Inverse Littlewood-Offord theory, Smooth Analysis and the Circular Law

-
Van Vu, Rutgers University
Fine Hall 224

A corner stone of the theory of random matrices is Wigner's semi-circle law, obtained in the 1950s, which asserts that (after a proper normalization) the limiting distribution of the spectra of a random hermitian matrix with iid (upper diagonal) entries follows the semi-circle law. The non-hermitian case is the famous Circular Law Conjecture, which asserts that (after a proper normalization) the limiting distribution of the spectra of a random matrix with iid entries is uniform in the unit circle.Despite several important partial results (Ginibre-Mehta, Girko, Bai, Edelman, Gotze-Tykhomirov, Pan-Zhu etc) the conjecture remained open for more than 50 years. Last year, T. Tao and I confirmed the conjecture in full generality. I am going to give an overview of this proof, which relies on rather surprising connections between various fields: combinatorics, probability, number theory and theoretical computer science. In particular, ideas from ADDITIVE COMBINATORICS play crucial roles.