You are currently browsing the tag archive for the ‘STOC’ tag.

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.]

### Recent Comments

 Rex on Distinguished Lecture Series I… Ocean Yu on The Riemann hypothesis in vari… Balazs Szegedy on Additive limits Anonymous on The “bounded gaps betwee… Sean Eberhard on Additive limits Benjamin Steinberg on A trivial generalisation of Ca… Benjamin Steinberg on A trivial generalisation of Ca… Benjamin Steinberg on A trivial generalisation of Ca… Sergio on Advice on mathematical careers… Mo Beans on Avila, Bhargava, Hairer, … A New Provable Facto… on The divisor bound Multiple Choice Ques… on On multiple choice questions i… A closed graph theor… on The closed graph theorem in va… Terence Tao on The Bourgain-Guth argument for… Frieder Ladisch on A trivial generalisation of Ca…