Approximate Spielman Teng theorems for the least singular value of random combinatorial matrices
An approximate Spielman Teng theorem for the least singular value s n M n of a random n x n square matrix M n is a statement of the following form: there exist constants C, c 0 such that for all e 0, Pr( s n M n e n C e 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.