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 \[P( σₙ(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.