On the Spielman-Teng Conjecture

Let $M$ be an $n\times n$ matrix with iid subgaussian entries with mean $0$ and variance $1$ and let ${\sigma }_n(M)$ denote the least singular value of $M$. We prove that $$\mathbb{P}({\sigma }_n(M)\le \epsilon n^{-1\mathrm{/}2})=(1+o(1))\epsilon +e^{-\mathrm{\Omega }(n)}$$ for all $0\le \epsilon \ll 1$. This resolves, up to a $1+o(1)$ factor, a seminal conjecture of Spielman and Teng.