We consider N × N symmetric one-dimensional random band matrices with general distribution of the entries and band width $W$.   The localization - delocalization conjecture predicts that there is a phase transition on the behaviors of  eigenvectors and  eigenvalues of the band matrices. It occurs at $W=N^{1/2}$. For wider-band matrix, the eigenvalues satisfied the so called sine-kernal distribution, and the eigenvectors are delocalized. With Bourgade, Yau and Fan, we proved that it holds when $W\gg N^{3/4}$. The previous best work required $W=\Omega(N).$ 

In their breakthrough 2011 paper, Chatterjee and Varadhan established a large deviations principle (LDP) for the Erdös-Rényi graph G(N,p), viewed as a measure on the space of graphons with the cut metric topology. This yields LDPs for subgraph counts, such as the number of triangles in G(N,p), as these are continuous functions of graphons. However, as with other applications of graphon theory, the LDP is only useful for dense graphs, with p ϵ (0,1) fixed independent of N. 

Since then, the effort to extend the LDP to sparse graphs with p ~ N^{-c} for some fixed c>0 has spurred rapid developments in the theory of "nonlinear large deviations". We will report on recent results increasing the sparsity range for the LDP, in particular allowing c as large as 1/2 for cycle counts, improving on previous results of Chatterjee-Dembo and Eldan. These come as applications of new quantitative versions of the classic regularity and counting lemmas from extremal graph theory, optimized for sparse random graphs. (Joint work with Amir Dembo.)

Conjugation invariant ensembles of random matrices have long formed one of the basic paradigms in Random Matrix Theory. Apart from the Gaussian case, the matrix elements of a conjugation invariant random matrix are highly correlated, and this fact has traditionally been viewed as prohibiting the use of moment methods in the spectral analysis of invariant ensembles. However, it turns out that there is a very natural and appealing version of the moment method available for these ensembles which seems to have been overlooked. I will describe the rudiments of this method, and some of its applications. Based on joint work with Sho Matsumoto.

Random matrices have become a very active area of research in the recent years and have found enormous applications in modern mathematics, physics, engineering, biological modeling, and other fields. In this work, we focus on symmetric sign (+/-1) matrices (SSMs) that were originally utilized by Wigner to model the nuclei of heavy atoms in mid-50s. Assuming the entries of the upper triangular part to be independent +/-1 with equal probabilities, Wigner showed in his pioneering works that when the sizes of matrices grow, their empirical spectra converge to a non-random measure having a semicircular shape. Later, this fundamental result was improved and substantially extended to more general families of matrices and finer spectral properties. In many physical phenomena, however, the entries of matrices exhibit significant correlations. At the same time, almost all available analytical tools heavily rely on the independence condition making the study of matrices with structure (dependencies) very challenging. The few existing works in this direction consider very specific setups and are limited by particular techniques, lacking a unified framework and tight information-theoretic bounds that would quantify the exact amount of structure that matrices may possess without affecting the limiting semicircular form of their spectra.

From a different perspective, in many applications one needs to simulate random objects. Generation of large random matrices requires very powerful sources of randomness due to the independence condition, the experiments are impossible to reproduce, and atypical or non-random looking outcomes may appear with positive probability. Reliable deterministic construction of SSMs with random-looking spectra and low algorithmic and computational complexity is of particular interest due to the natural correspondence of SSMs and undirected graphs, since the latter are extensively used in combinatorial and CS applications e.g. for the purposes of derandomization. Most of the existing constructions of pseudo-random graphs focus on the extreme eigenvalues and do not provide guaranties on the whole spectrum. In this work, using binary Golomb sequences, we propose a simple completely deterministic construction of circulant SSMs with spectra converging to the semicircular law with the same rate as in the original Wigner ensemble. We show that this construction has close to lowest possible algorithmic complexity and is very explicit. Essentially, the algorithm requires at most 2log(n) bits implying that the real amount of randomness conveyed by the semicircular property is quite small.

Random matrix theory began with the study, by Wigner in the 1950s, of high-dimensional matrices with i.i.d. entries (up to symmetry).  The empirical law of eigenvalues demonstrates two key phenomena: bulk universality (the limit empirical law of eigenvalues doesn't depend on the laws of the entries) and concentration (the convergence is robust and fast).

Several papers over the last decade (initiated by Bryc, Dembo, and Jiang in 2006) have studied certain special random matrix ensembles with structured correlations between some entries. The limit laws are different from the Wigner i.i.d. case, but each of these models still demonstrates bulk universality and concentration.

In this lecture, I will talk about very recent results of mine and my students on these general phenomena:

Bulk universality holds true whenever there are constant-width independent bands, regardless of the correlations within each band.  (Interestingly, the same is not true for independent rows or columns, where universality fails.)  I will show several examples of such correlated band matrices generalizing earlier known special cases, demonstrating how the empirical law of eigenvalues depends on the structure of the correlations.

At the same time, I will show that concentration is a more general phenomenon, depending not on the the structure of the correlations but only on the sizes of correlated partition blocks. Under  some regularity assumptions, we find that Gaussian concentration occurs in NxN ensembles so long as the correlated blocks have size smaller than N^2/log(N).