See also: arXiv page, ORCID profile and Google Scholar profle.

My research is supported by the NSF.

Current interests:
  • Large deviations for random graphs and random matrices; connections with models for disordered systems in statistical physics, and the regularity method in extremal graph theory and additive combinatorics;
  • The universality phenomenon in random matrix theory (and the mysterious appearance of random matrix distributions in physics and analytic number theory);
  • Extreme values of log-correlated fields; connections to random matrices, number theory, branching processes and PDE (the Fisher–KPP equation and related reaction-diffusion systems);
  • Pseudospectrum for random non-normal operators; related topics in geometric functional analysis, random matrix theory and free probability.
Papers and preprints (including some informal descriptions):
  • Full large deviation principles for the largest eigenvalue of sub-Gaussian Wigner matrices arXiv
    slides video
    Preprint.
  • Typical structure of sparse exponential random graph models arXiv
    slides
    with Amir Dembo.
    video
    Annals of Applied Probability, to appear.
  • Universality of Poisson limits for moduli of roots of Kac polynomials / arXiv journal /
    diapositivas (en español)
    with Hoi H. Nguyen, Oren Yakir and Ofer Zeitouni.
    Int. Math. Res. Not, 2023(8):6648-6690, 2022.
    Description Building on our previous works on the minimum modulus for random polynomials (see work with Nguyen below and of Yakir and Zeitouni here) we give a new proof of a recent resolution by Michelen and Sahasrabudhe of a conjecture of Shepp and Vanderbei: that the moduli of roots of Gaussian Kac polynomials of degree n, centered at 1 and rescaled by n^2, should form a Poisson point process. We use this new approach to verify a conjecture of Michelen and Sahasrabudhe that the Poisson statistics are in fact universal.
  • Regularity method and large deviation principles for the Erdős–Rényi hypergraph arXiv
    slides
    Duke Math Journal, to appear.
    Description The "infamous upper tail" problem, as it was popularized by Janson and Rucinski, is to estimate (to leading exponential order) the probability that the number of copies of a fixed graph H in the Erdős–Rényi graph G(n,p) exceeds its expectation by a constant factor. After a long line of works, an essentially optimal result for the case that H is a regular graph was recently obtained in work of Harel, Mousset and Samotij by a beautiful truncated moment method argument, along with further refinements for the case of bipartite regular H by Basak and Basu.

    In this work we are interested in the extent to which more powerful Large Deviation Principle (LDP) type statements hold, in the more general setting of r-uniform hypergraphs. Classically, an LDP concerns a sequence of probability measures in a topological space, giving asymptotics at exponential scale for the probability of fixed sets in the topology. The general topological setting allows for the formulation of LDPs for infinite dimensional objects such as paths of stochastic processes. It can also be useful for studying measures on spaces of increasing finite dimension, provided they can be embedded in a common topological space.

    This was done in the context of random graphs of increasing size in the seminal work of Chatterjee and Varadhan establishing the LDP for the sequence of Erdős–Rényi distributions, viewed as measures on graphon space. The topological space of graphons is in some sense the completion of the set of all finite graphs of all sizes under a metric induced by the cut norm. Joint upper and lower tail estimates for continuous functionals on graphon space follow by applying the LDP to intersections of level sets. Crucially, subgraph counts extend to continuous (nonlinear) functionals on graphon space – a qualitative version of the classic counting lemma in extremal graph theory. In this way, the Chatterjee–Varadhan LDP addresses the infamous upper tail problem, and much more.

    Graphon theory provides a qualitative, topological reformulation of the classic "finite-n" regularity method in extremal graph theory, which rests on two key lemmas: Szemerédi's regularity lemma, which underlies the compactness of graphon space, and the counting lemma.

    Unfortunately, the Chatterjee–Varadhan LDP, and graphon space in general, is only useful for studying sequences of dense graphs, with a non-vanishing proportion of the possible edges (in particular G(n,p) with p fixed independent of n). While there are theories of sparse graph limits, such as L^p-graphons, these are not useful for the study of large deviations without a suitable sparse counting lemma. And, while various sparse counting lemmas have been developed – see for instance this work of Conlon, Fox and Zhao and references therein – these impose "pseudorandom container" hypotheses that make them unsuitable for the large deviations problem.

    In this work, we bypass the problem of developing an appropriate space of limiting objects for framing a classical LDP, and instead develop a sparse regularity method for hypergraphs, allowing for quantitative LDP-type statements at finite n for the r-uniform Erdős–Rényi hypergraph of density p which may vanish at certain polynomial rates in n. The method uses a new class of tensor norms that generalize the cut norm, as well as generalizations for hypergraphs considered by Gowers in his seminal work on the multidimensional Szemerédi theorem. These norms are designed to be able to detect "localization phenomena" that are responsible for upper-tail deviations of subgraph counts in sparse hypergraphs (and which also underlie some of the problems for developing a useful class of limiting objects for sparse graph sequences). Under these norms we obtain a decomposition theorem for arbitrary tensors with bounded entries, generalizing the classic Frieze–Kannan decomposition for matrices (closely related to the so-called weak regularity lemma and the compactness of graphon space); as well as an accurate sparse counting lemma. The decomposition theorem easily yields the LDP-type statements giving asymptotics for the measure assigned to general sets of hypergraphs, and the counting lemma allows for the application to level sets of subgraph counting functions to get joint tail asymptotics. (These in turn are useful in the study of certain Gibbs measures on graphs known as exponential random graph models, which are widely applied in the social sciences.)

    For the application to upper/lower tails for counts of copies of hypergraphs H of max-degree D, the LDPs allow p to decay like n^{-1/(D+1)}, with a faster speed for certain H. It seems that n^{-1/D} is the limit for validity of LDP-type statements for general events. However, in the case of upper tails for counts of D-regular graphs in the Erdős–Rényi graph (r=2), the above mentioned works of Harel–Mousset–Samotij and Basak–Basu manage to push the exponent further to essentially 2/D, which is the optimal range for the so-called "naïve mean-field" asymptotic we obtain; furthermore, an essentially optimal sparsity range for the lower-tail problem for hypergraph counts was recently obtained by a beautiful entropy argument by Kozma and Samotij. These works succeed in leveraging additional properties of super/sub-level sets, whereas the decomposition theorem and LDPs are blind to such properties and apply equally to general sets.
  • Universality of the minimum modulus for random trigonometric polynomials journal/arXiv
    slides (English)
    Discrete analysis, 2021:20, 46 pp.
    video
    Description It has been shown in recent work of Yakir and Zeitouni that the minimum modulus of random trigonometric polynomials with Gaussian coefficients has a limiting exponential distribution. We show this is a universal phenomenon. Our approach relates the joint distribution of small values of the polynomial at a fixed number m of points on the circle to the distribution of a certain random walk in a 4m-dimensional phase space. Under Diophantine approximation conditions on the angles, we obtain strong small ball estimates and a local central limit theorem for the distribution of the walk.
  • Spectrum and pseudospectrum for quadratic polynomials in Ginibre matrices / arXiv journal /
    slides
    with Alice Guionnet and Jonathan Husson.
    Ann. Inst. H. Poincaré, Probab. Statist., 58(4):2284–2320, 2022.
    Description The circular law, going back to work of Ginibre in the 1960s and established in its most general form by Tao and Vu in 2008, describes the spectral distribution of random NxN matrices with iid entries. For the general case the problem reduced to the study of scalar random walks – i.e. the dot product of a row of the matrix with a normal vector to the span of remaining rows. The main challenge was to rule out certain arithmetic structure in the normal vector, which was accomplished by results of Tao and Vu and in essentially optimal form by Rudelson and Vershynin.

    However, it remains a challenge to extend this understanding to polynomials in iid matrices. Free probability theory provides a prediction for the limiting spectral distribution as the Brown measure of the polynomial evaluated at freely independent circular operators in a von Neumann algebra. As a first step, we establish this prediction for the degree-two case. As was the case for the circular law for iid matrices, the main technical hurdle is to obtain quantitative control on the pseudospectrum for the polynomial at finite N. Via a linearization trick of Haagerup–Thorbjørnsen we reduce to proving anti-concentration for determinants of random walks in a matrix space of bounded dimension. Here there is a new layer not present in the scalar case for the circular law: we need to rule out that the walk concentrates in a singular subspace of matrices, a task which takes up the bulk of the paper. The main challenge is that the matrix entries have a strong dependency structure determined by the polynomial under consideration – in particular it is difficult to treat all polynomials in a unified way.

    These difficulties are orthogonal to the arithmetic obstacles for the general circular law, and we take the matrices to be Gaussian – the "nicest" distribution – in order to focus on these novel challenges (and keep the paper of reasonable length!). In our opinion at least, the extension to higher degree would be more interesting than to general distributions.
  • Non-Hermitian random matrices with a variance profile (II): Properties and examples / arXiv journal /
    with Walid Hachem, Jamal Najim and David Renfrew.
    J. Theor. Probab. (2021).
    Description Part (I) was devoted to a general result establishing existence of a sequence of deterministic equivalent measures for the random spectral distributions, determined by a nonlinear system of Schwinger–Dyson equations. That result applies for a broad class of variance profiles and does not even require the corresponding sequence of spectral measures to converge. Here we investigate settings in which the sequence converges to a limiting distribution, and establish some general properties for the limiting measures.
  • Large deviations of subgraph counts for sparse Erdős–Rényi graphs / arXiv journal /
    with Amir Dembo. slides
    Adv. Math, 373 (October 28, 2020).
    Description An influential work of Chatterjee and Dembo initiated a general study of quantitative large deviations principles for nonlinear functionals on product spaces. Their approach goes through the closely related study of Gibbs measures, and covers many examples including subgraph-counting functionals on the product space of graphs with the Erdös–Rényi measure, and counts of k-term arithmetic progressions in sparse random subsets of the integers. Here we develop a different and more direct approach for the setting of subgraph-counts for random graphs. The basic approach (which applies quite generally, not just to graphs) is to efficiently cover super-level sets of the functional under consideration with "small" convex sets. The motivation for this strategy is that the so-called naïve mean-field approximation for the upper tail holds as a (non-asymptotic!) upper bound for convex sets, so with a small enough covering one can conclude with a simple union bound. In the Gibbs measure picture, the idea is that the naïve mean-field bound holds if one can show the metric entropy of level sets is negligible compared to the free energy for an associated Gibbs measure.

    For the specific setting of Erdös–Rényi graphs we construct efficient coverings by a spectral approach, approximating the corresponding adjacency matrices with low-rank matrices, and approximating the latter with a net of spectral-norm balls. There is a further technical step to show that subgraph-counts are sufficiently regular with respect to the spectral norm. This was straightforward for cycle counts, which can be expressed as moments of the spectral distribution, and in particular require no study of eigenvectors, but additional arguments were required to extend to general subgraph counts. Around the same time, Fanny Augeri independently established similar results for the case of cycle counts, also making use of spectral truncation arguments. While she did not cover general subgraph counts, her argument was sharper for the case of triangle counts.

    With hindsight, we realized that our covering approach can be viewed as a quantitative version of the large deviations principle for the Erdös–Rényi measure established in work of Chatterjee and Varadhan. Classical large deviations principles are formulated on topological measure spaces, and the Chatterjee–Varadhan LDP is with respect to the graphon topology, based on the cut norm. Their results for upper tails rest on the compactness of graphon space, coming from Szemerédi's regularity lemma, and the continuity of subgraph-counting functionals in the cut-norm topology, which in extremal graph theory is known as the counting lemma. Our argument neatly divides into a net construction (quantitative compactness) and a continuity estimate (counting lemma), with respect to the spectral norm rather than the cut norm.

    Our approach applies to any functional on the Erdös–Rényi measure space that is sufficiently regular in the spectral norm, such as edge eigenvalues, and also yields joint upper tails for collections of such functionals, as shown in subsequent work of Bhattacharya and Dembo. However, for counts of a single subgraph, much more precise upper tail asymptotics, valid in an essentially optimal range of sparsity, have since been obtained in beautiful work of Harel, Mousset and Samotij, with further extensions for bipartite graphs by Basak and Basu. These results are based on refined analysis of high level sets of the subgraph-counting functionals, showing that an excess of subgraphs is due to the appearance of a "core" structure in the graph – a localized concentration of excess edges, such as a clique. This lets one efficiently cover super-level sets of subgraph-counting functionals with a small number of sets – one for each possible core – and conclude via the union bound.
  • Maximum for the characteristic polynomial of a random permutation matrix / arXiv journal /
    slides with Ofer Zeitouni.
    Commun. Pure Appl. Math, 73: 1660–1731, 2020.
    Description Motivated by the Fyodorov–Hiary–Keating conjecture for the maximum modulus of the Riemann zeta function on a randomly shifted interval on the critical line, lately there has been extensive work on establishing the corresponding result for the maximum modulus over the unit circle of the characteristic polynomial of CUE matrices – random unitary matrices drawn from the normalized Haar measure. CUE matrices have been observed to model the zeta function since the work of Montgomery and Dyson. In this work we study the corresponding problem for matrices drawn uniformly from a discrete subgroup: the set of permutation matrices. We establish the leading order, at logarithmic scale, for the maximum modulus of uniform random permutation matrices, analogous to a result of Arguin, Belius and Bourgade for CUE matrices, and Arguin, Belius, Bourgade, Radziwill and Soundararajan for the zeta function. As with those work, our argument follows the paradigm for extremes of logarithmically correlated fields going back to work of Bramson's 1978 work on branching Brownian motion.

    In contrast to the CUE field, which is stationary under rotations of the plane, in the discrete setting the random field at points on the circle has different behavior depending on proximity to roots of unity, requiring separate treatment on "major" and "minor" arcs. In particular, we borrow arguments from the Hardy–Littlewood circle method in order to rule out certain arithmetic conspiracies in the fine behavior on minor arcs. Another difference from the CUE field is that the tails are asymptotically Poissonian rather than Gaussian, and a careful conditioning argument is needed to rule out certain "resonances" stemming from Poisson clumping in the cycle structure of the permutation.
  • Circular law for the sum of random permutation matrices / arXiv journal /
    slides
    with Anirban Basak and Ofer Zeitouni.
    Electronic Journal of Probability, 23:paper no. 33, 51 pp., 2018.
  • The circular law for random regular digraphs. / arXiv journal /
    slides
    Ann. Inst. H. Poincaré, Probab. Statist., 55(4):2111–2167, 2019.
  • Non-Hermitian random matrices with a variance profile (I): Deterministic equivalents and ESDs / arXiv journal /
    slides
    with Walid Hachem, Jamal Najim and David Renfrew.
    Electronic Journal of Probability, 23:paper no. 110, 61 pp., 2018.
    Description The circular law gives the limiting spectral distribution for random matrices with iid entries. We generalize this to matrices with independent entries having non-identical variances, as specified by a deterministic "variance profile". A key feature of our results is to allow sparse profiles, with an arbitrary proportion of entries set to zero deterministically, which we can do provided they satisfy a certain quantitative irreducibility property. An important step is to obtain quantitative bounds on the solutions to an associated system of Schwinger–Dyson equations, which we accomplish in the general sparse setting using a novel graphical bootstrap argument.
  • Spectral properties of non-Hermitian random matrices. UC open access
    PhD Thesis, UCLA.
  • Lower bounds for the smallest singular value of structured random matrices. / arXiv journal /
    Ann. Probab., 46(6):3442–3500, 2018.
  • Size biased couplings and the spectral gap for random regular graphs / arXiv journal /
    with Larry Goldstein and Toby Johnson.
    Ann. Probab., 46(1):72–125, 2018.
  • The circular law for random regular digraphs with random edge weights. / arXiv journal /
    Random Matrices: Theory Appl., 06, 1750012, 2017.
  • Discrepancy properties for random regular digraphs. / arXiv journal /
    Random Struct. Algor., 50:23–58, 2016.
  • On the singularity of adjacency matrices for random regular digraphs. / arXiv journal /
    Probab. Theory Relat. Fields, 167(1):143--200, Feb 2017.

Talk slides/videos:

  • Large deviations theory for random graphs. slides
    Mathematics and Statistics Dept. Colloquium, UNC Greensboro, Oct 2023
  • Large deviations for the largest eigenvalue of sub-Gaussian Wigner matrices. slides
    High Dimensional Statistics and Random Matrices, Porquerolles, June 2023
  • Structure and stability for sparse exponential random graphs. slides
    video
  • Universalidad en los extremos de polinomios aleatorios. diapositivas (en español)
  • Large deviations and the regularity method for the Erdős–Rényi (hyper)graph. slides
    video
  • Universality for the minimum modulus of random trigonometric polynomials. slides
    video
  • Pseudospectra of structured random matrices. slides
    Random matrices workshop, Oberwolfach, Dec 2019
  • Large deviations for sparse random graphs. slides
    Random matrices and random graphs workshop, CIRM, Luminy, Apr 2019
  • Large deviations of subgraph counts for sparse random graphs. slides
    Amir Dembo’s 60th birthday conference, Stanford, Dec 2018
  • Pseudospectrum and spectral anti-concentration: Beyond mean field models. slides
    IPAM QLA Culminating Workshop, Lake Arrowhead, CA, June 2018
  • The maximum of the characteristic polynomial for a random permutation matrix. slides
    Random matrices and free probability workshop, IPAM, UCLA, May 2018
  • Circular laws for random regular digraphs. slides
    AMS Fall Western Sectional Meeting, UC Riverside, Nov 2017
  • Inhomogeneous circular laws for random matrices with non-identically distributed entries. slides
    Probability and Mathematical Physics Seminar, UC Davis, April 2017
  • Random regular digraphs: singularity and spectrum. slides
    Probability Seminar, Stanford, Nov 2015