On the Spielman-Teng Conjecture

Let M be an n n matrix with iid subgaussian entries with mean 0 and variance 1 and let ₙ (M) denote the least singular value of M. We prove that (₍ (M) n^-1/2) = (1+o (1) ) + e^- (n) \ for all 0 1. This resolves, up to a 1+o (1) factor, a seminal conjecture of Spielman and Teng.