**
Welcome to the Einstein Institute of Mathematics**

Home | About | Staff | Studies | Colloquia & Events | Research | Services & Resources | Sites |

Erdős Lectures in Discrete Mathematics and Theoretical Computer Science

**
Random discrete matrices**

*Prof. Van H. Vu* (Rutgers University)

**Random discrete matrices I**

Thursday, May 24th, at 16:00, Lecture Hall 2**Random discrete matrices II:***Random walks, lazy random walks and the singularity problem*

Friday, May 25th, at 11:00, room 110**Random discrete matrices III:***From smooth analysis to circular law: A journey via additive combinatorics*

Sunday, May 27th, at 10:00, room 110

Light refreshments will be served before each of the talks

**Random discrete matrices I**- Random matrices is an important area of mathematics, with strong
connections to many other areas (mathematical physics, combinatorics,
theoretical computer science, to mention a few).
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.

**Random discrete matrices II:***Random walks, lazy random walks and the singularity problem*- I will discuss recent developments concerning the following question:

"What is the probability that a random Bernoulli matrix is singular ?"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 .999^{n}. 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.

**Random discrete matrices III:***From smooth analysis to circular law: A journey via additive combinatorics*- It was observed in the 1950s that the eigenvalues of a (non-Hermittian)
random matrix seem to distribute uniformly in a circle (circular law).
A rigorous explanation was given by Ginibre/Mehta (60s) for the Gaussian
case, and by Bai (1997, following a work of Girko from 1984) for general
continuous models. Bai's proof, however, does not extend to the
discrete models.
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.

Cambridge : Cambridge University Press, c2006.

Back to the Math home page

Mathematics and Computer Science Library | Faculty of Science | The Hebrew University of Jerusalem |

Background image © copyright 1997 by Xah Lee, used with permission.