Random Matrix & Probability Theory Seminar (2016-2017)

The random matrix and probability theory will be every Wednesday from 3pm-4pm in CMSA Building, 20 Garden Street, Room G10.



Date Name Title/Abstract
02-15-17 Lisa Hartung, Courant Institute


Title: The Structure of Extreme Level Sets in Branching Brownian Motion

Abstract: Branching Brownian motion (BBM) is a classical process in probability, describing a population of particles performing independent Brownian motion and branching according to a Galton Watson process. Arguin et al.\ and A\”\i{}d\’ekon et al.\ proved the convergence of the extremal process. In the talk we discuss how one can obtain finer results on the extremal level sets by using a random walk-like representation of the extremal particles. We establish among others the upper tail probabilities for the distance between the maximum and the second maximum (joint work with Aser Cortines and Oren Louder).

02-22-17 Bob Hough, Stony Brook University

Bob Hough

Title: Random walk on unipotent groups

Abstract: I will describe results of two recent papers from random walk on unipotent groups.  In joint work with Diaconis (Stanford), we obtain a new local limit theorem on the real Heisenberg group, and determine the mixing time of coordinates for some random walks on finite unipotent groups.  In joint work with Jerison and Levine (Cornell) we prove a cut-off phenomenon in sandpile dynamics on the torus $(\mathbb{Z}/m\mathbb{Z})^2$ and obtain a new upper bound on the critical exponent of sandpiles on $\mathbb{Z}^2$.

03-01-17 Shirshendu Ganguly, UC Berkeley


Title:  Large deviation and counting problems in sparse settings

Abstract: The upper tail problem in the Erd ̋os-R ́enyi random graph G ∼ Gn,p, where every edge is included independently with probability p, is to estimate the probability that the number of copies of a graph H in G exceeds its expectation by a factor 1 + δ. The arithmetic analog considers the count of arithmetic progressions in a random subset of Z/nZ, where every element is included independently with probability p. In this talk, I will describe some recent results regarding the solution of the upper tail problem in the sparse setting, i.e. where p decays to zero, as n grows to infinity. The solution relies on non-linear large deviation principles developed by Chatterjee and Dembo and more recently by Eldan and solutions to various extremal problems in additive combinatorics.

03-08-17  Xiaoqin Guo, Purdue University

xiaoqin Guo

Title: Harnack inequality for a balanced random environment

Abstract: We consider a random walk in a balanced random environment on $Z^d$ which is allowed to be non-elliptic. This is a Markov chain generated by a discrete non-divergence form operator. In this talk, assuming that the environment is iid and “genuinely d-dimensional”, we will present a Harnack inequality for discrete harmonic functions of the corresponding operator. The result is based on the analysis of the percolation structure of the (non-reversible) environment and renormalization arguments.

Joint work with N. Berger, J.-D. Deuschel and M.Cohen.

03-15-17 Chiranjib Mukherjee, New York University

Chiranjib Mukherjee

03-22-17 Alexander Fribergh, University of Montreal Title: The ant in the labyrinth

Abstract: One of the most famous open problem in random walks in random environments is to understand the behavior of a simple random walk on a critical percolation cluster, a model known as the ant in the labyrinth. I will present new results on the scaling limit for the simple random walk on the critical branching random walk in high dimension. In the light of lace expansion, we believe that the limiting behavior of this model should be universal for simple random walks on critical structures in high dimensions.

03-24-17 Chiranjib Mukerjee, Courant Institute

Chiranjib Mukherjee

Title: Compactness and Large Deviations

Abstract: In a reasonable topological space, large deviation estimates essentially deal with probabilities of events that are asymptotically (exponentially) small, and in a certain sense, quantify the rate of these decaying probabilities. In such estimates, upper bounds for such small probabilities often require compactness of the ambient space, which is often absent in problems arising in statistical mechanics (for example, distributions of local times of Brownian motion in the full space Rd). Motivated by such a problem, we present a robust theory of “translation-invariant compactication” of probability measures in Rd. Thanks to an inherent shift-invariance of the underlying problem, we are able to
apply this abstract theory painlessly and solve a long standing problem in statistical mechanics, the mean-eld polaron problem.

This talk is based on joint works with S. R. S. Varadhan (New York), as well as with Erwin Bolthausen (Zurich) and Wolfgang Koenig (Berlin).

03-29-17 Nina Holden, MIT


Title: Percolation-decorated triangulations and their relation with SLE and LQG

Abstract: The Schramm-Loewner evolution (SLE) is a family of random fractal curves, which is the proven or conjectured scaling limit of a variety of two-dimensional lattice models in statistical mechanics, e.g. percolation. Liouville quantum gravity (LQG) is a model for a random surface which is the proven or conjectured scaling limit of discrete surfaces known as random planar maps (RPM). We prove that a percolation-decorated RPM converges in law to SLE-decorated LQG in a certain topology. This is joint work with Bernardi and Sun. We then discuss a work in progress where we try to strengthen the topology of convergence of a RPM to LQG by considering conformal embeddings of the RPM into the complex plane. This is joint work with Sun and with Gwynne, Miller, Sheffield, and Sun.


NOTE: This talk will be held in room G02

04-05-17 Steven Heilman, UCLA


Title: Noncommutative Majorization Principles and Grothendieck’s Inequality

Abstract: The seminal invariance principle of Mossel-O’Donnell-Oleszkiewicz implies the following. Suppose we have a multilinear polynomial Q, all of whose partial derivatives are small. Then the distribution of Q on i.i.d. uniform {-1,1} inputs is close to the distribution of Q on i.i.d. standard Gaussian inputs. The case that Q is a linear function recovers the Berry-Esseen Central Limit Theorem. In this way, the invariance principle is a nonlinear version of the Central Limit Theorem. We prove the following version of one of the two inequalities of the invariance principle, which we call a majorization principle. Suppose we have a multilinear polynomial Q with matrix coefficients, all of whose partial derivatives are small. Then, for any even K>1, the Kth moment of Q on i.i.d. uniform {-1,1} inputs is larger than the Kth moment of Q on (carefully chosen) random matrix inputs, minus a small number. The exact statement must be phrased carefully in order to avoid being false. Time permitting, we discuss applications of this result to anti-concentration, and to computational hardness for the noncommutative Grothendieck inequality. (joint with Thomas Vidick)


Oanh Nguyen, Yale University

Title: Roots of random polynomials

Abstract: Random polynomials, despite their simple appearance, remain a mysterious object with a large number of open questions that have attracted intensive research for many decades. In this talk, we will discuss some properties of random polynomials including universality and asymptotic normality. I will also talk about some interesting open questions. The talk is based on joint works with Yen Do, Hoi Nguyen, and Van Vu.

Note: This talk will take place from 2:00-3:00pm

04-12-17 Subhajit Goswami, University of Chicago


Title: Liouville first-passage percolation and Watabiki’s prediction

Abstract: In this talk I will give a brief introduction to Liouville first-passage percolation (LFPP) which is a model of random metric on a finite planar grid graph. It was studied primarily as a way to make sense of the random metric associated with Liouville quantum gravity (LQG), one of the major open problems in contemporary probability theory. I will discuss some recent results on this metric and the main focus will be on estimates of the typical distance between two points. I will also discuss about the apparent disagreement of these estimates with a prediction made in the physics literature about LQG metric. The talk is based on a joint work with Jian Ding.

04-19-17 Weijun Xu, University of Warwick

Weijun Xu

Title: Meaing of infinities in KPZ and Phi^4_3

Abstract: Many interesting stochastic PDEs arising from statistical physics are ill-posed in the sense that they involve products between distributions, so the solutions to these equations are obtained after renormalisations, which typically change the original equation by a quantity that is infinity. I will use KPZ and Phi^4_3 as two examples to explain the meanings of these infinities. As a consequence, we will see how these two equations, interpreted after suitable renormalisations, arise naturally as (weakly) universal limits for two distinct classes of systems. Part of the talk based on joint works with Martin Hairer, Cyril Labbe and Hao Shen.

04-26-17 Ashkan Nikeghbali, University of Zurich
05-03-17 Ilya Soloveychik, Harvard University/Hebrew University of Jerusalem


Title:  Deterministic Random Matrices

Abstract: In many applications researchers and engineering need to simulate random symmetric sign (+/-1) matrices (Wigner’s matrices). The most natural way to generate an instance of such a matrix is to toss a fair coin, fill the upper triangular part of the matrix with the outcomes and reflect it part into the lower triangular part. For large matrix sizes such approach would require a very powerful source of randomness due to the independence condition. In addition, when the data is generated by a truly random source, atypical non-random looking outcomes have non-zero probability of showing up. Yet another issue is that any experiment involving tossing a coin would be impossible to reproduce exactly, which may be crucial in computer scientific applications.

In this talk we focus on the problem of generating n by n symmetric sign matrices based on the similarity of their spectra to Wigner’s semicircular law. We develop a simple completely deterministic construction of symmetric sign matrices whose spectra converge to the semicircular law when n grows to infinity. The Kolmogorov complexity of the proposed algorithm is as low as 2 log (n) bits implying that the real amount of randomness conveyed by the semicircular property is quite small.


Date Name Title
09-21-16 Stephane Benoist, MIT


 Title: Near critical spanning forests

Abstract: We study random spanning forests in the plane, which are slight perturbations of a uniformly chosen spanning tree (UST) and come with a natural fragmentation dynamics. We show how to relate the scaling limit of these forests to the stationary distribution of a natural Markov process on a state space of abstract graphs with edge-weights. This abstract graph setup could be fruitful for using renormalization ideas. In this point of view, our dynamics on forest corresponds to a repulsive direction around the UST fixed point.

This is a joint work with Laure Dumaz (CNRS, Paris-Dauphine) and Wendelin Werner (ETH Zürich).

09-28-16 Antonio Auffinger, Northwestern


Title: Parisi formula for the ground state energy of the Sherrington-Kirkpatrick model

Abstract: Spin glasses are disordered spin systems originated from the desire of understanding strange magnetic behaviors of certain alloys in physics. As mathematical objects, they are often cited as examples of complex systems and have provided several fascinating structures and conjectures. In this talk, we will focus on the Sherrington-Kirkpatrick spin glass model. We will present the Parisi formula and some properties for the maximum energy. In addition, we will discuss some representations of the Parisi Formula in terms of stochastic optimal control problems. This talk is based on recent joint works with Wei-Kuo Chen. 

10-05-16 Edgar Dobriban, Stanford


Title: Computation, statistics and random matrix theory

Abstract: Random matrices are useful models for large datasets. The Marchenko-Pastur (1967) ensemble for general covariance matrices is an increasingly used modeling framework that captures the effects of correlations in the data, with numerous statistical applications.

In this talk we discuss the fruitful interactions between computation, statistics and random matrix theory in this area. We explain a fundamental computational problem in RMT: computing the limit empirical spectral distribution (ESD) of general covariance matrices. Our recent Spectrode method solves this problem efficiently. As an application, we solve a challenging problem in theoretical statistics. We construct optimal statistical tests based on linear spectral statistics to detect principal components below the phase transition. We also describe the software we are building for working with large random matrices, which we hope will broaden reach of RMT.

10-12-16 Michael Damron, Georgia Tech


Title: Bigeodesics in first-passage percolation

Abstract: In first-passage percolation, we place i.i.d. continuous weights at the edges of Z^2 and consider the weighted graph metric. A distance minimizing path between points x and y is called a geodesic, and a bigeodesic is a doubly-infinite path whose segments are geodesics. It is a famous conjecture that almost surely, there are no bigeodesics. In the `90s, Licea and Newman showed that, under a curvature assumption on the “asymptotic shape,” all infinite geodesics have asymptotic directions and there are no bigeodesics with both ends directed in some deterministic subset D of [0,2pi) with countable complement. I will discuss recent work with Jack Hanson in which we show that there are no bigeodesics with one end directed in any deterministic direction, assuming the shape boundary is differentiable. This rules out existence of ground state pairs for the related disordered ferromagnet whose interface has a deterministic direction. Furthermore it resolved the Benjamini-Kalai-Schramm “midpoint problem” under the additional assumption of differentiability.


Dmitry Panchenko, University of Toronto


Title: Free energy in the non-homogeneous SK model and SK model with vector spins.

Abstract: I will describe some ideas behind the Parisi formula for the free energy in the classical Sherrington-Kirkpatrick model and explain how these ideas can be extended to compute the free energy in two versions of the model: (a) with non-homogeneous interactions and (b) with vector spins, for example, the Potts spin glass.

 10-24-16 (Monday!) Sebastien Bubeck, Microsoftsebastien-bubeck-chapo_vignette

Title: Local max-cut in smoothed polynomial time


The local max-cut problem asks to find a partition of the vertices in a weighted graph such that the cut weight cannot be improved by moving a single vertex (that is the partition is locally optimal). This comes up naturally, for example, in computing Nash equilibrium for the party affiliation game. It is well-known that the natural local search algorithm for this problem might take exponential time to reach a locally optimal solution. We show that adding a little bit of noise to the weights tames this exponential into a polynomial. In particular we show that local max-cut is in smoothed polynomial time (this improves the recent quasi-polynomial result of Etscheid and Roglin).

Joint work with Omer Angel, Yuval Peres, and Fan Wei.

10-26-16  Wei Wu, NYUpic-wei-wu-280

Title: Extremal and local statistics for gradient field models

Abstract: The gradient field models with uniformly convex potential (also known as the Ginzburg-Landau field) is believed to be in the Gaussian universality class, and has been applied to study different lattice models. Previous work by Naddaf-Spencer and by Miller proved the macroscopic averages of the field converge to a continuum Gaussian free field. In this talk we will describe recent progresses to understand the maximum and local statistics of the field, that indicates the Gaussian universality holds in a strong sense.


Ramon van Handel, Princeton


Title: Inhomogeneous random matrices

Abstract: How do random matrices behave when the entries can have an arbitrary variance pattern? New problems arise in this setting that are almost completely orthogonal to classical random matrix theory. I will illustrate such problems by describing one of my favorite conjectures on this topic due to R. Latala, and the various mathematical techniques and questions that are emerging from its investigation.



Boaz Barak, Harvard

Screen Shot 2016-09-06 at 11.13.15 AM

TITLE: Computational Bayesianism, sums of squares, cliques, and unicorns


Can we make sense of quantities such as “the probability that 2^81712357 – 1 is prime” or “the probability that statement X is a logical contradiction”?

More generally, can we use probabilities to quantify our “computational uncertainty”  in cases where all the relevant information is given but in a computationally hard-to-extract form?

In this talk we will discuss how such “pseudo probabilities” can arise from the Sum of Squares (SOS) semidefinite program (Parrilo’00, Lasserre’01).

We will show how this yields an approach for showing both positive and negative results for the SOS algorithms.

In particular we will present better algorithms for the tensor decomposition problem from data analysis, and stronger lower bounds for the planted clique problem.

The talk will be partially based on joint works with Sam Hopkins, Jon Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin and David Steurer.

I will not assume any prior knowledge on the sum of squares algorithm or semidefinite programming.

11-16-16 Yu Gu, Stanford



Title: Local vs global random fluctuations in stochastic homogenization

Abstract: We will discuss stochastic homogenization of elliptic equations in divergence form, of which the probabilistic counterpart is the random conductance model. I will try to explain some probabilistic and analytic approaches we use to obtain the first and higher order random fluctuations. It turns out that in high dimensions, a formal two-scale expansion only leads to the correct “local” fluctuation, but not the “global” one. Part of the talk is based on joint work with Jean-Christophe Mourrat.


NOTE Date Change: Tuesday

Jafar Jafarov, Stanford


Title: SU(N) Wilson loop expectations

Abstract: Lattice gauge theories are discrete approximations to quantum Yang-Mills theories. The main object of interest in lattice gauge theories are Wilson loop expectations. I will present 1/N expansion for SU(N) Wilson loop expectations in strongly coupled SU(N) lattice gauge theory in any dimension. I will show how to represented the coefficients of the expansion as absolutely convergent sums over trajectories in a string theory on the lattice, establishing a kind of gauge-string duality.



James Lee, University of Washington


TITLE:  Conformal growth rates, spectral geometry, and distributional limits of graphs


Given a graph, one can deform its geometry according to a function that assigns non-negative weights to the vertices.  We refer to this as a “conformal” deformation of the graph metric.  For a finite graph, it makes sense to define the area of such a weight as the average of the squared weights of the vertices.  One can similarly define the area of a conformal weight for a unimodular random graph.

The conformal growth exponent is the smallest rate of volume growth of balls achievable by a conformal weight of unit area.  We show that if a unimodular (rooted) random graph (G,x) has quadratic conformal growth (QCG) and the law of deg(x) is sufficiently well-behaved, then the random walk on G is almost surely recurrent.  We also argue that our joint with Kelner, Price, and Teng (2011) can be used to show that every distributional limit of finite planar graphs has QCG.  More generally, this holds for H-minor-free graphs, and other interesting families like string graphs (the intersection graph of continuous arcs in the plane).  These methods do not rely on circle packings, and can instead be thought of as directly uniformizing the underlying graph metric.  They yield a short proof of Benjamini and Schramm’s result that a distributional limit of finite, bounded-degree planar graphs is almost surely recurrent, and provide a positive answer to their conjecture that the same should hold for H-minor-free graphs.

Gurel-Gurevich and Nachmias recently solved a central open problem by showing that the uniform infinite planar triangulation (UIPT) and quadrangulation (UIPQ) are almost surely recurrent.  By combining QCG with methods from spectral geometry, we present a new proof of this fact that follows from strong quantitative bounds on the heat kernel.

A similar phenomenon holds beyond dimension two:  Assuming the law of deg(x) has tails that decay faster than any inverse polynomial, the almost sure spectral dimension of a unimodular random graph (G,x) is equal to its conformal growth exponent.  This has consequences for limits of graphs that can be sphere-packed in R^d for d > 2.

 12-07-16 Dan Romik, UC Davis


Title: A Pfaffian point process for Totally Symmetric Self Complementary Plane Partitions

Abstract: Totally Symmetric Self Complementary Plane Partitions (TSSCPPs) can be encoded as a family of nonintersecting lattice paths having fixed initial points and variable endpoints. The endpoints of the paths associated with a uniformly random TSSCPP of given order therefore induce a random point process, which turns out to be a Pfaffian point process. I will discuss conjectural formulas for the entries of the correlation kernel of this process, and a more general “rationality phenomenon”, which if true implies the existence of an interesting limiting process describing “infinite TSSCPPs” as well as conjectural probabilities for the occurrence of certain connectivity patterns in loop percolation (a.k.a. the dense O(1) loop model).

 12-14-16  Brian Rider, Temple

Title: Universality for the random matrix hard edge

Abstract: The hard edge refers to the distribution of the smallest singular value for certain ensembles of random matrices, or, and what is the same, that of the minimal point of a logarithmic gas constrained to the positive half line. For any inverse temperature and “quadratic” potential the possible limit laws (as the dimension, or number of particles, tends to infinity) was characterized by Jose Ramirez and myself in terms of the spectrum of a (random) diffusion generator. Here we show this picture persists for more general convex polynomial potentials. Joint work with Patrick Waters.


Related Posts