9:00 – 9:30
Registration/Breakfast
9:30 – 9:40
Opening Remarks
9:40 – 10:40
Amir Dembo, Extremal Cuts of Sparse Random Graphs
The Max-Cut problem seeks to determine the maximal cut size in a given graph. With no polynomial-time efficient approximation for Max-Cut (unless P=NP), its asymptotics for a typical large sparse graph are of considerable interest. We prove that for the uniformly random d-regular graph of N vertices, and for the uniformly chosen Erdos-Renyi graph of M=N d/2 edges, the leading correction to M/2 (the typical cut size) is P_* sqrt(N M/2). Here P_* is the ground state energy of the Sherrington-Kirkpatrick model, expressed analytically via Parisi’s formula. This talk is based on a joint work with Subhabrata Sen and Andrea Montanari.
10:50 – 11:50
Ivan Corwin, Integrable probability and the KPZ universality class
The Gaussian central limit theorem says that for a wide class of stochastic systems, the bell curve (Gaussian distribution) describes the statistics for random fluctuations of important observables. In this talk I will look beyond this class of systems to a collection of probabilistic models which include random growth models, particle systems, optimization problems, matrices and stochastic PDEs. I will explain how through certain “integrable” or “exactly solvable” examples we are able to see how these different examples all fall into a single universality class — the KPZ class — with a much richer mathematical structure than that of the Gaussian. This talk is expository and meant for a wide audience without any background in these areas.
11:50 – 1:00
Lunch
1:00 – 2:00
Dmitry Chelkak, 2D Ising model: discrete s-holomorphicity and correlation functions
In the first part of this talk we discuss the notion of discrete s-holomorphic functions on a general weighted planar graph. Similarly to the fact that all problems on random walks (classical, in random environment, on random graphs, etc) have the same underlying structure of discrete harmonic functions, the notion of s-holomorphicity is naturally associated with the 2D nearest-neighbor Ising model — the famous model of a ferromagnet with plus-minus spins introduced by Lenz in 1920. In the second part, we give a brief overview of convergence theorems obtained recently for various correlation functions in the critical 2D Ising model considered on discrete approximations to a given planar domain (joint works with Hongler, Izyurov and Smirnov). These results can be viewed as a justification of predictions made by physicists in 1980s via Conformal Field Theory techniques, as well as an alternative route to derive these explicit formulas for the correlation functions.
2:10 – 3:10
James Lee, A variational view on the decay of entropy, in reverse
If one watches the evolution of a Markov process to stationarity, information about the initial distribution is progressively lost. We study the behavior of certain processes (especially at “early” times) by playing this video in reverse. The reversal is described formally by the Doob h-transform and yields another (time inhomogeneous) Markov process.
There is a precise sense in which the reversed process is the entropically optimal way of constructing the initial distribution. We present two applications of this variational perspective. The first is based on joint work with Ronen Eldan; we resolve the Gaussian case of Talagrand’s convolution conjecture (1989). The second application is to new log-Sobolev inequalities for for some Glauber dynamics on finite graphs.
3:10 – 4:00
Afternoon break
4:00 – 5:00
Ryan O’Donnell, Quantum tomography and random Young diagrams
In quantum mechanics, the state rho of a d-dimensional particle is given by a d x d PSD matrix of trace 1. The “quantum tomography problem” is to estimate rho accurately using as few “copies” of the state as possible. The special case of “quantum spectrum estimation” involves just estimating the eigenvalues alpha_1, …, alpha_d of rho, which form a probability distribution. By virtue of some representation theory, understanding these problems mostly boils down to understanding certain statistics of random words with i.i.d. letters drawn from the alpha_i distribution. These statistics involve longest increasing subsequences, and more generally, the shape of Young tableaus produced by the Robinson-Schensted-Knuth algorithm. In this talk we will discuss new probabilistic, combinatorial, and representation-theoretic tools for these problems, and the consequent new upper and lower bounds for quantum tomography. This is joint work with John Wright (Carnegie Mellon University).
5:00
Event ends