  An approximate Spielman-Teng theorem for the least singular value $s_n(M_n)$
of a random $n\times n$ square matrix $M_n$ is a statement of the following
form: there exist constants $C,c >0$ such that for all $\eta \geq 0$,
$\Pr(s_n(M_n) \leq \eta) \lesssim n^{C}\eta + \exp(-n^{c})$. The goal of this
paper is to develop a simple and novel framework for proving such results for
discrete random matrices. As an application, we prove an approximate
Spielman-Teng theorem for $\{0,1\}$-valued matrices, each of whose rows is an
independent vector with exactly $n/2$ zero components. This improves on
previous work of Nguyen and Vu, and is the first such result in a `truly
combinatorial' setting.
