The March 14 lecture will take place at 4:00 p.m. and will be preceded by a 3:00 reception in the 4th floor lounge of the CoRE Building.
| March 14, 4 p.m. Reception: 3 p.m. |
Szemerédi's regularity lemma revisited
In 1975, Szemerédi introduced a remarkable regularity lemma for large dense graphs, as a key component of his proof of a long-standing conjecture of Erdős and Turán on arithmetic progressions. Roughly speaking, this lemma asserts that any large dense graph can be modeled accurately by a bounded number of random graphs between a bounded number of cells in a vertex partition. This lemma has since proven to be of major importance in graph theory, computer science, and combinatorial number theory. In recent years, the regularity lemma (and its generalisation to hypergraphs) has been revisited using several new perspectives, including functional analysis, measure theory, non-standard analysis, information theory, and ergodic theory; for instance, these approaches to the regularity lemma played an important guiding role in my work with Ben Green on establishing arbitrarily long arithmetic progressions in the primes. We discuss some of these new developments and insights in this talk. |
| March 17, 10 a.m. | Singularity and Determinant of
Discrete Random Matrices
Consider a large random matrix M in which all entries are identically and independently drawn from a discrete distribution (e.g. uniformly chosen at random from {-1,+1}). How likely is M to be singular (non-invertible)? As a related question, how is the determinant det(M) of M distributed? We discuss some results of Kahn-Komlós-Szemerédi, Tao-Vu, Costello-Tao-Vu, and others towards understanding these questions. The techniques used are a combination of Euclidean geometry, linear algebra, Fourier analysis, geometry of numbers, and combinatorics. In particular, the Littlewood-Offord problem (how often does a discrete random walk return to the origin?), or more precisely the inverse Littlewood-Offord problem (if a random walk returns often to the origin, what does this tell us about the walk?) plays a pivotal role. |
| March 18, 11:30 a.m. | Least Singular Value of Discrete Random Matrices
In many applications, knowing that a random matrix M is invertible is not enough; one also needs to understand how large the inverse is (or to control closely related quantities, such as the condition number or the least singular value). For this more quantitative task, one needs to use "robust" versions of the technologies discussed in the first lecture. In particular, the inverse problem for the small ball probability (how often does a random walk return to a small ball?) becomes central. We will discuss some recent work of Rudelson-Vershynin and Tao-Vu in understanding these issues. |
| March 19, 11:30 a.m. |
Eigenvalue Distributions of Discrete Random Matrices
In the third lecture we consider the full spectral distribution of the (complex) eigenvalues of a (non-selfadjoint) random matrix M, and their limiting value as the size of the matrix goes to infinity. Due to the lack of self-adjointness, many standard techniques, such as the moment method, do not work well. Instead one needs to study other transforms of this distribution, such as the quantity log|det (M-zI)| for various complex numbers z, as pioneered by Girko and then formalised by Bai, Girko, and others. In order to execute this strategy for discrete matrices, the results from the previous two lectures are needed. We survey some recent developments by Gotze-Tikhomorov, Pan-Zhou, Tao-Vu and others on this topic. |
The previous Lewis lectures are listed below.
| Lecturer | Date | Title |
| Stephen Smale | March 1984 | The Topology of Classical Algorithms |
| G. D. Mostow | March 1985 | Braids, Hypergeometric Functions, and Lattices |
| Lipman Bers | October 1985 | Teichmüller Theory for Beginners |
| David Kazhdan | March 1987 | Representations of Reductive P-Adic Groups |
| H. Blaine Lawson | April 1988 | Algebraic Cycles |
| Paul Rabinowitz | April 1989 | Periodic Solutions of Hamiltonian Systems |
| Yasha G. Sinai | April 1990 | Random Behavior of Eigenvalues of Laplacians |
| Jurgen Moser | March 1991 | Stability in Dynamics and Minimal Solutions in the Calculus of Variations |
| L. Craig Evans | March 1992 | Compactness for Solutions of Nonlinear Partial Differential Equations |
| Ian Macdonald | March 1993 | Symmetric Functions and Orthogonal Polynomial |
| V. I. Arnold | November 1993 | On Some Problems in Singularity Theory |
| Karen Uhlenbeck | September 1994 | Moduli Spaces of Solutions to PDE |
| Alain Connes | April 1996 | Gravity Coupled with Matter and the Foundation of Noncommutative Geometry |
| Don Zagier | March 1997 | Modular Forms and Differential Operators |
| Yves Meyer | March 2000 | Wavelets
and Image Processing: Theory and Application to Denoising Hubble
Space Telescope Images;
Oscillations, Vibrations, Time-Frequency Analysis and the Virgo Program (Detection of Gravitational Waves); The Role of Oscillations in Some Non-Linear Evolution Equations: Application to Navier-Stokes Equations |
| Graeme Segal | April 2001 | The
Mathematical Structure of Quantum Field Theory;
Quantum Field Theory and K-Theory; Quantum Field Theory and Representation Theory |
| Richard P. Stanley | October, 2002 |
Six Recent Developments in Algebraic Combinatorics:
The Laurent phenomenon; longest increasing subsequences The Saturation Conjecture; the n! Conjecture Gromov-Witten invariants; graphical degree sequences |
| Jean-Michel Coron | October, 2003 | Controllability and nonlinearity for some flow control systems |
| Shmuel Weinberger | October 2004 | Themes in
Quantitative Topology:
Problems and naive examples Computation, entropy, and variational problems Embeddings, symmetry, and rigidity |
| Andrei Okounkov | April, 2007 | Moduli of Curves and Combinatorics |