On the condition number of a randomly perturbed matrix

Let $M$ be an arbitrary $n$ by $n$ matrix. We study the condition
number  a random perturbation $M+N_n$ of $M$, where $N_n$ is a
random matrix, motivated by a problem raised by  Spielman and Teng. It is
shown that, under very general conditions on
$M$ and $N_n$, the condition number  of $M+N_n$ is polynomial in
$n$ with very high probability.


The main novelty here is that we
allow $N_n$ to have discrete distributions. Discreteness posed a
considerble mathematical challenge which we were able to overcome by
bringing in ideas and tools from additive combinatorics. The core of our
proof is the so-called Inverse Littlewood-Offord theorem which
characterizes all integer sequences with many colliding subsums.

Joint work with T. Tao (UCLA)