Title: What Could Push the Edge Far from the Bulk of the Spectrum of Random Matrices?

We survey here the various mechanisms we know that can break the well known fact that for a random matrix the top eigenvalues stick to the bulk. We will survey the influence of heavy tails, of finite rank perturbations and of sparseness of the entries. This will use results from joint works with Antonio Auffinger, Jinho Baik, Alice Guionnet and Sandrine Peche.

Title: Linear Statistics of Eigenvalues and Stein's Method

I will present an abstract central limit theorem with total variation error bounds for linear statistics of eigenvalues of random matrices. The technique, based on Stein's method, gives a unified tool for a large class of matrices. I will show applications to Wigner, Wishart, Double Wishart, and Toeplitz matrices. The CLT for Toeplitz matrices, as well as the error bounds for the other cases, are new results.

Title: The Rank of Random Symmetric Matrice

Let Q(n,p) be a random symmetric matrices whose entries above the main diagonal are independently either 1 (with probability p) or 0 (with probability 1-p). We will examine the following questions (whose answer will depend on p):

(1) What is the singularity probability of Q?

(2) If Q is likely to be singular, how can we (almost surely) describe  
the dependent sets of rows?

Joint with Van Vu (Rutgers) and Terence Tao (UCLA).

Title: Random Matrix Theory: Origins, Theory, Applications and some Open Problems

The speaker will describe how RMT emerged as a tool in theoretical physics and in mathematics. He will also discuss some of the techniques that arise in the analysis of RMT statistics and illustrate the appplication of RMT with some examples. He will also describe a few open problems.

Title: From Random Matrices to Random Analytic Functions

Peres and Virag proved that the zeros of the power series a_0+za_1+z^2a_2+... with i.i.d. standard complex Gaussian coefficients, is a determinantal point process on the unit disk, invariant in distribution under isometries of the hyperbolic plane. Extending this result, I show that the singular points of the matrix-valued power series A_0+zA_1+z^2A_2+..., where A_i are k x k matrices with i.i.d. standard complex Gaussian entries, is also a determinantal process in the disk. This gives a unified framework in which to view the result of Peres and Virag and a well-known theorem of Ginibre on Gaussian random matrices.

Title: Fast Computation of Low Rank Matrix Approximations using Randomized Matrices

We study the problem of computing a matrix of low rank that approximates a given input matrix well. This can typically be dominated by many matrix-vector multiplications, whose cost grows linearly with the number of entries in the source matrix. We show that several randomized matrix simplifications, such as randomized sparsification and quantization, can substantially improve the running time of this computation without greatly impacting the quality of the low rank approximation. We present perturbation analysis bounding the influence that the introduced errors can have, and see empirically that the results are even better than the bounds imply, suggesting further work to more tightly characterize the affect of perturbations on low rank approximations.

Title: Random Matrices with Linear Structure

Traditionally the theory of random matrices has focused mainly on matrices whose entries are all independent random matrices, except possibly for a self-adjointness constraint. In a 1999 survey, Bai suggested studying the asymptotic spectral behavior of random matrices which lie in one of several smaller linear subspaces of the space of matrices, in particular Toeplitz, Hankel and Markov matrices. I will discuss recent results on these and other ensembles of random matrices with linear structure.

Title: Dyck Paths and Random Matrices: the Moment Method

We will speak about the moment approach in random matrix theory, developed by A. Soshnikov for instance to prove universality of the fluctuations of the largest eigenvalues of certain ensembles of random matrices. If Dyck paths are suitable objects to handle traces of Wigner matrices, the suitables tools to investigate traces of sample covariance matrices are "Narayana paths", that is Dyck paths with a certain number of odd up steps.

Title: Norm of the Inverse of a Random Matrix

Let $A$ be an $n \times n$ matrix with independent entries. It is well known that under appropriate moment assumptions, the norm of $A$ is of order $\sqrt{n}$ with high probability. It was long believed that the same holds for $A^{-1}$. This was only known for Gaussian matrices, and was conjectured for Bernoulli matrices (with independent $\pm 1$ entries). We prove this conjecture in full generality, for matrices with general independent entries, and under mild moment assumptions. Moreover, for any $\e > e^{-c n}$ we obtain a bound on the norm of $A^{-1}$, which holds with probability $1-\e$, and show that such bound is optimal.

We will also extend these results to rectangular random matrices. (Joint with R. Vershynin).

Title: Free Probability and Random Matrices

I will give an introduction to free probability theory, with emphasis on its relation to combinatorics (via non-crossing partitions) and random matrices.

Title: Graph Sparsification by Effective Resistances

A sparsifier of a graph is a sparse subgraph whose Laplacian quadratic form approximates the quadratic form of the original. Sparsifiers provide a natural notion of what it means to approximate a graph by a sparse subgraph, and may be used as preconditioners for solving systems of linear equations. We show that one can obtain a high-quality sparsifier of a graph by sampling every edge of the graph with probability proportional to its effective resistance. We then explain how these sparsifiers can be constructed in nearly-linear time.

This is joint work with Nikhil Srivastava.

I. Singularity and Determinant of Random Matrices

II. Least Singular Value of Random Matrices

III. Eigenvalue Distributions of Random Matrices

Title: I. Singularity and Determinant of Random Matrices

Title: Logconcave Random Graphs

We propose the following model of a random graph on $n$ vertices. Let F be a distribution in R_+^{n(n-1)/2} with a coordinate for every pair ij with 1 \le i,j \le n. Then G_{F,p} is the distribution on graphs with n vertices obtained by picking a random point X from F and defining a graph on n vertices whose edges are pairs ij for which X_{ij} \le p. The standard Erd\H{o}s-R\'{e}nyi model is the special case when F is uniform on the 0-1 unit cube. We determine basic properties such as the connectivity threshold for quite general distributions. We also consider cases where the X_{ij} are the edge weights in some random instance of a combinatorial optimization problem. By choosing suitable distributions, we can capture random graphs with interesting properties such as triangle-free random graphs and weighted random graphs with bounded total weight.

Title: Concentration and the Littlewood-Offord Problem

The classical concentration inequalities of probability theory demonstrate that nice random variables are typically concentrated about their means. Less studied but often needed is the reverse phenomenon -- that the concentration can not be too tight.

The Littlewood-Offord Problem asks: how much can a sum of independent random variables concentrate? I will discuss a sharp result joint with Mark Rudelson which clasiffies the obstacles in the Littlewod-Offord Problems via additive combinatorics. This leads to a proof of two basic conjectures on invertibility of random matrices, which will be the content of the talk by Mark Rudelson.

Title: On the Singular Probability of Random Discrete Matrices

Let $n$ be a large integer and $M_n$ be an $n$ by $n$ random matrix whose entries are independent (but not necessarily identically distributed) random variables taking at most $n^{o(n)}$ values in the complex numbers. The main goal of this paper is to prove a general upper bound for the probability that $M_{n}$ is singular.

For a constant $0< p< 1$ and a constant positive integer $r$, we will define aproperty called $p$-bounded of exponent $r$. Our main result shows that if the entries of $M_n$ satisfy this property, then the probability that $M_n$ is singular is at most $(p^{1/r} + o(1))^n$. Here are a few sample corollaries of this theorem:

(1) If the distribution of each entry has mass at most p on a single point, then the singular probability is at most 
$p+o(1))^{n/2}. in the special case of random Bernoulli matrices, this improves the previous bound $(3/4+o(1))^n$ of Tao and Vu. 


(2) If the entries are iid with distribution which puts mass 1/2 on 0 and 1/4 on -1 and 1, then the singular probability is at most 
$(1/2+o(1))^n$. This bounds is sharp, as the probability of having a zero row is (1/2+o(1))^n. 

The proof refines the approach from Kahn-Komlos-Szemeredi and Tao-Vu and makes a critical use of Tao-Vu inverse theorem.

(Joint work with J. Bourgain and V. Vu).

Title: Local Dependencies in Random Matrices, the LLN, and Algebraicity

We consider random matrices whose entries are locally dependent. We prove the convergence of the spectral measure, and characterize the limit by means of a system of (algebraic) equations. Study of these equations yields some analytic information on the limit density.

(joint work with G. W. Anderson).