This week I am in San Diego for the 39th ACM Symposium for the Theory of Computing (STOC). Today I presented my work with Van Vu on the condition number of randomly perturbed matrices, which was the subject of an earlier post on this blog. For this short talk (20 minutes), Van and I prepared some slides; of course, in such a short time frame one cannot hope to discuss many of the details of the result, but one can at least convey the statement of the result and a brief sketch of the main ideas in the proof.

One late update (which didn’t make it onto the slides): last week, an alternate proof of some cases of our main result (together with some further generalisations and other results, in particular a circular law for the eigenvalues of discrete random matrices) was obtained by Pan and Zhou, using earlier arguments by Rudelson and Vershynin.

[Update, June 16: It was pointed out to me that the Pan-Zhou result only recovers our result in the case when the unperturbed matrix has a spectral norm of O(n^{1/2}) (our result assumes that the unperturbed matrix has polynomial size). Slides also updated.]