| COMPUTER SCIENCE/DISCRETE MATH I | |
| Topic: | On the Condition Number of a Randomly Perturbed Matrix |
| Speaker: | Van Vu |
| Affiliation: | Rutgers, The State University of New Jersey |
| Date: | Monday, January 22 |
| Time/Room: | 11:15am - 12:15pm/West Building Lecture Theatre |
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 considerable 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)