The Hebrew University of Jerusalem

Welcome to the Einstein Institute of Mathematics

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

Center for Theoretical Computer Science and Discrete Mathematics
Erdős Lectures in Discrete Mathematics and Theoretical Computer Science

The Hebrew University Center for Theoretical Computer Science and Discrete Mathematics invites you to this year's Erdős Lecture in Discrete Mathematics and Theoretical Computer Science

Random discrete matrices

Prof. Van H. Vu (Rutgers University)

Location: Einstein Institute of Mathematics
Lectures:
1. Random discrete matrices I
Thursday,   May 24th, at 16:00,   Lecture Hall 2
2. Random discrete matrices II: Random walks, lazy random walks and the singularity problem
Friday,   May 25th, at 11:00,   room 110
3. 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
Abstracts:

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 .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.

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.

Reference:
Additive combinatorics / Terence Tao, Van Vu.
Cambridge : Cambridge University Press, c2006.