Welcome to the Einstein Institute of Mathematics
Home | About | Staff | Studies | Colloquia & Events | Research | Services & Resources | Sites |
Random discrete matrices
Prof. Van H. Vu (Rutgers University)
Basically, there are two types of random matrices: continuous and discrete. The continuous models (such as Gaussian) have an established theory. On the other hand, the discrete models (such as Bernoulli/Rademacher) are still not very well understood.
In this talk, we discuss a few basic problems (such as rank, determinant, smallest singular value, circular law etc). An emphasis will be put on a new and non-trivial relation to additive combinatorics, discovered recently by T.Tao and myself. This relation leads to several notable progresses.
The conjectured bound here is (1/2+o(1))n, basically the probability that there are two equal rows. In 1995, Kahn, Komlos and Szemeredi proved the first exponential bound .999n. Few years ago, Tao and I improved the bound to (3/4+o(1))n, based on an inverse theorem about the returning probability of a random walk. I will focus on this bound but also discuss few even more recent improvements and extensions.
Another observation in a completely different area: linear programming. It is a very well known phenomenon in the programming community that the simplex method, while proven to be exponential in the worst case, usually runs very fast, beating all other algorithms, even those are proven to be polynomial in all cases. Few years ago, Spielman and Teng came up with a nice explanation (smooth analysis) which relies on the existence of noise in the calculation process. Their analysis assumed continuous noise. The proof for the discrete (and more natural) case has been missing.
I will discuss recent developments which fill these missing parts, using tools from additive combinatorics, in particular the so-called Inverse Littlewood-Offord theorem.