The random matrix and probability theory will be every Wednesday from 3pm4pm in CMSA Building, 20 Garden Street, Room G10.
Date  Name  Title/Abstract 
021517  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 walklike 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). 
022217  Bob Hough, Stony Brook University 
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 cutoff 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$. 
030117  Shirshendu Ganguly, UC Berkeley  Title: Large deviation and counting problems in sparse settings
Abstract: The upper tail problem in the Erd ̋osR ́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 nonlinear large deviation principles developed by Chatterjee and Dembo and more recently by Eldan and solutions to various extremal problems in additive combinatorics. 
030817  Xiaoqin Guo, Purdue University  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 nonelliptic. This is a Markov chain generated by a discrete nondivergence form operator. In this talk, assuming that the environment is iid and “genuinely ddimensional”, 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 (nonreversible) environment and renormalization arguments. Joint work with N. Berger, J.D. Deuschel and M.Cohen. 
031517  Chiranjib Mukherjee, New York University  POSTPONED DUE TO WEATHER 
032217  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. 
032417  Chiranjib Mukerjee, Courant Institute  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 “translationinvariant compactication” of probability measures in Rd. Thanks to an inherent shiftinvariance of the underlying problem, we are able to 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). 
032917  Nina Holden, MIT  Title: Percolationdecorated triangulations and their relation with SLE and LQG
Abstract: The SchrammLoewner evolution (SLE) is a family of random fractal curves, which is the proven or conjectured scaling limit of a variety of twodimensional 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 percolationdecorated RPM converges in law to SLEdecorated 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 
040517  Steven Heilman, UCLA  Title: Noncommutative Majorization Principles and Grothendieck’s Inequality
Abstract: The seminal invariance principle of MosselO’DonnellOleszkiewicz 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 BerryEsseen 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 anticoncentration, and to computational hardness for the noncommutative Grothendieck inequality. (joint with Thomas Vidick) 
041217 
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:003:00pm 
041217  Subhajit Goswami, University of Chicago 
Title: Liouville firstpassage percolation and Watabiki’s prediction Abstract: In this talk I will give a brief introduction to Liouville firstpassage 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. 
041917  Weijun Xu, University of Warwick  Title: Meaing of infinities in KPZ and Phi^4_3
Abstract: Many interesting stochastic PDEs arising from statistical physics are illposed 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. 
042617  Ashkan Nikeghbali, University of Zurich  
050317  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 nonrandom looking outcomes have nonzero 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 
092116  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 edgeweights. 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, ParisDauphine) and Wendelin Werner (ETH Zürich). 
092816  Antonio Auffinger, Northwestern 
Title: Parisi formula for the ground state energy of the SherringtonKirkpatrick 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 SherringtonKirkpatrick 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 WeiKuo Chen. 
100516  Edgar Dobriban, Stanford 
Title: Computation, statistics and random matrix theory Abstract: Random matrices are useful models for large datasets. The MarchenkoPastur (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. 
101216  Michael Damron, Georgia Tech  Title: Bigeodesics in firstpassage percolation
Abstract: In firstpassage 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 doublyinfinite 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 BenjaminiKalaiSchramm “midpoint problem” under the additional assumption of differentiability. 
101916 
Dmitry Panchenko, University of Toronto

Title: Free energy in the nonhomogeneous 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 SherringtonKirkpatrick model and explain how these ideas can be extended to compute the free energy in two versions of the model: (a) with nonhomogeneous interactions and (b) with vector spins, for example, the Potts spin glass. 
102416 (Monday!)  Sebastien Bubeck, Microsoft 
Title: Local maxcut in smoothed polynomial time Abstract: The local maxcut 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 wellknown 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 maxcut is in smoothed polynomial time (this improves the recent quasipolynomial result of Etscheid and Roglin). Joint work with Omer Angel, Yuval Peres, and Fan Wei. 
102616  Wei Wu, NYU 
Title: Extremal and local statistics for gradient field models Abstract: The gradient field models with uniformly convex potential (also known as the GinzburgLandau field) is believed to be in the Gaussian universality class, and has been applied to study different lattice models. Previous work by NaddafSpencer 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. 
110216 
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. 
110916
TIME CHANGE: 2:50PM 
TITLE: Computational Bayesianism, sums of squares, cliques, and unicorns ABSTRACT: 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 hardtoextract 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. 

111616  Yu Gu, Stanford
TIME CHANGE: 2:30PM 
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 twoscale expansion only leads to the correct “local” fluctuation, but not the “global” one. Part of the talk is based on joint work with JeanChristophe Mourrat. 
112216
NOTE Date Change: Tuesday 
Jafar Jafarov, Stanford 
Title: SU(N) Wilson loop expectations Abstract: Lattice gauge theories are discrete approximations to quantum YangMills 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 gaugestring duality. 
113016
ROOM CHANGE: G02 
James Lee, University of Washington 
TITLE: Conformal growth rates, spectral geometry, and distributional limits of graphs ABSTRACT: Given a graph, one can deform its geometry according to a function that assigns nonnegative 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 wellbehaved, 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 Hminorfree 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, boundeddegree planar graphs is almost surely recurrent, and provide a positive answer to their conjecture that the same should hold for Hminorfree graphs. GurelGurevich 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 spherepacked in R^d for d > 2. 
120716  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). 
121416  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. 