Seminars & Events for Probability Seminar

September 21, 2016
3:00pm - 4:00pm
Loop erased random walk, uniform spanning tree, and bi-Laplacian Gaussian field in the critical dimension

Critical lattice models are believed to converge to a free field in the scaling limit, at or above their critical dimension. This has been (partially) established for Ising and Phi^4 models for d \ge 4. We describe a simple spin model from uniform spanning forests in Z^d whose critical dimension is 4 and prove that the scaling limit is the bi-Laplacian Gaussian field for d\ge 4. At dimension 4, there is a logarithmic correction for the spin-spin correlation and the bi-Laplacian Gaussian field is a log correlated field. The proof also improves the known mean field picture of LERW in d=4: we show that the renormalized escape probability (and arm events) of 4D LERW converge to some "continuum escaping probability". Based on joint works with Greg Lawler and Xin Sun.

Speaker: Wei Wu , Courant Institute/NYU
Location:
Fine Hall 214
September 28, 2016
3:00pm - 4:00pm
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 asymptotic for a typical large sparse graph is of considerable interest.  We prove that for 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.

Speaker: Amir Dembo , Stanford University
Location:
Fine Hall 214
October 12, 2016
3:00pm - 4:00pm
Detecting geometric structure in random graphs

We study the problem of detecting the presence of an underlying high-dimensional geometric structure in a random graph. Under the null hypothesis, the observed graph is a realization of an Erdos-Renyi random graph. Under the alternative, the graph is a geometric random graph, where each vertex corresponds to a latent independent random vector uniformly distributed on the d-dimensional sphere (the isotropic case) or a Gaussian distribution with an arbitrary covariance matrix (the non isotropic case), and two vertices are connected if the corresponding latent vectors are close enough. In the dense regime (i.e., p is a constant), we propose a near-optimal and computationally efficient testing procedure based on a new quantity which we call signed triangles.

Speaker: Ronan Eldan, Weizmann Institute
Location:
Fine Hall 214
October 19, 2016
3:00pm - 4:00pm
Speed of random walks on finitely generated groups

We discuss a flexible construction of groups where the speed (rate of escape) of simple random walk can follow any sufficiently nice function between diffusive and linear. When the speed of the \mu-random walk is sub-linear, all bounded \mu-harmonic functions are constant. We investigate the minimal growth of non-constant harmonic functions on these groups and show it is tightly related to the speed of the random walk. Based on joint works with Jeremie Brieussel, Gidi Amir and Gady Kozma.

Speaker: Tianyi Zheng , UCSD
Location:
Fine Hall 214
October 26, 2016
3:00pm - 4:00pm
Stationary Aggregation Processes

In this talk I'll introduce stationary versions of known aggregation models e.g., DLA, Hastings Levitov, IDLA and Eden. Using the additional symmetry and ergodic theory, one obtains new geometric insight on the aggregation processes.

Speaker: Eviatar Procaccia , Texas A&M University
Location:
Fine Hall 214
November 9, 2016
3:00pm - 4:00pm
Universal asymptotic behavior of discrete particle systems beyond integrable cases

The talk is about a class of systems of 2d statistical mechanics, such as random tilings, noncolliding walks, log-gases and random matrix-type distributions. Specific members in this class are integrable, which means that available exact formulas allow delicate asymptotic analysis leading to the Gaussian Free Field, sine-process, Tracy-Widom distributions. Extending the results beyond the integrable cases is challenging. I will speak about a recent progress in this direction: about universal local limit theorems for a class of lozenge and domino tilings, noncolliding random walks; and about GFF-type asymptotic theorems for global fluctuations in these systems and in discrete beta log-gases.

Speaker: Vadim Gorin , MIT
Location:
Fine Hall 214
November 30, 2016
3:00pm - 4:00pm
Finding and hiding the seed

I will present an overview of recent developments in source detection and estimation in randomly growing graphs and diffusions on graphs. Can one detect the influence of the initial seed graph? How good are root-finding algorithms? Can one engineer messaging protocols that hide the source of a rumor? I will explore such questions in the talk. This is based on joint works with Sebastien Bubeck, Ronen Eldan, Elchanan Mossel, Jacob Richey, and Tselil Schramm.

Speaker: Miklos Racz , Microsoft
Location:
Fine Hall 214
December 7, 2016
3:00pm - 4:00pm
The spectral gap of dense random regular graphs

Let G be uniformly distributed on the set of all simple d-regular graphs on n vertices, and assume d is bigger than some (small) power of n. We show that the second largest eigenvalue of G is of order √d with probability close to one. Combined with earlier results covering the case of sparse random graphs, this settles the problem of estimating the magnitude of the second eigenvalue, up to a multiplicative constant, for all values of n and d, confirming a conjecture of Van Vu. Joint work with Pierre Youssef.

Speaker: Konstantin Tikhomirov , Princeton University
Location:
Fine Hall 214
December 14, 2016
3:00pm - 4:00pm
Gaussian complex zeros on the hole event: the emergence of a forbidden region

Consider the Gaussian Entire Function (GEF) whose Taylor coefficients are independent complex-valued Gaussian variables, and the variance of the k-th coefficient is 1/k!. This random Taylor series is distinguished by the invariance of its zero set with respect to the isometries of the complex plane.  I will show that the law of the zero set, conditioned on the GEF having no zeros in a disk of radius r, and properly normalized, converges to an explicit limiting Radon measure in the plane, as r goes to infinity. A remarkable feature of this limiting measure is the existence of a large 'forbidden region' between a singular part supported on the boundary of the (scaled) hole and the equilibrium measure far from the hole.

Speaker: Alon Nishry , University of Michigan
Location:
Fine Hall 214
February 8, 2017
3:00pm - 4:00pm
Random walk on free solvable groups

The study of free solvable groups has been advocated and pursued by Anatoly Vershik and others with various perspectives in mind. I will discuss random walks on free finitely generated solvable groups in the general context of geometric group theory and with an emphasize on exploring what algebraic properties are reflected in the behavior of various random walk. (Joint work with Tianyi Zheng)

Speaker: Laurent Saloff-Coste, Cornell University
Location:
Fine Hall 214
February 22, 2017
3:00pm - 4:00pm
Diffusive estimates for random walk under annealed polynomial growth

We show that on a random infinite graph G of polynomial growth where simple random walk is stationary, it is diffusive along a subsequence, i.e., the second moment of the distance from the starting point grows linearly in time. This extends a result of Kesten that applied to the extrinsic metric on subgraphs of the lattice Zd, and answers a question due to Benjamini, Duminil-Copin, Kozma and Yadin. We also show that, in general, passing to a subsequence is necessary. As a consequence, we deduce that harmonic functions of sublinear growth on such graphs G are constants. Our proof combines embeddings with the mass transport principle. Based on joint work with James Lee and Yuval Peres.

Speaker: Shirshendu Ganguly , Berkeley
Location:
Fine Hall 214
March 8, 2017
3:00pm - 4:00pm
The 2D Coulomb gas and the Gaussian free field

We prove a quantitative central limit theorem for linear statistics of particles in the complex plane, with Coulomb interaction at any temperature. This generalizes works by Rider, Virag, Ameur, Hendenmalm and Makarov obtained for the integrable model at inverse temperature beta=2. Important tools are a multi scale analysis and the loop equation. This is joint work with Roland Bauerschmidt, Miika Nikula and Horng-Tzer Yau.

Speaker: Paul Bourgade , Courant Institute/NYU
Location:
Fine Hall 214
March 15, 2017
3:00pm - 4:00pm
Variance-sensitive concentration inequalities and Dvoretzky's theorem

The cornerstone of Asymptotic Geometric Analysis is the celebrated theorem of Dvoretzky on almost-spherical sections of high-dimensional convex bodies. The critical dimension at which spherical sections appear, on an isomorphic scale, was settled by V. Milman's seminal work in the 70's. On the other hand, the dimension on the almost-isometric scale (in the existential or in the random case) is far from being understood.  Motivated by questions arising in the study of this problem, we are going to discuss a variance-sensitive concentration inequality for convex functions of Gaussian vectors. Time permitting we will discuss recent developments on Dvoretzky's theorem for special classes of bodies. The talk will be based on joint works with Petros Valettas.

Speaker: Grigoris Paouris , Texas A&M University
Location:
Fine Hall 214
March 29, 2017
3:00pm - 4:00pm
Singular values of random band matrices: Marchenko-Pastur law and more

We consider the limiting spectral distribution of matrices of the form (R+X)(R+X)^∗/(2b_n+1), where X is an n by n band matrix of bandwidth b_n and R is a non random band matrix of bandwidth b_n. We show that the Stieltjes transform of spectrum of such matrices converges to the Stieltjes transform of a non-random measure. And the limiting Stieltjes transform satisfies an integral equation. For R=0, the integral equation yields the Stieltjes transform of the Marchenko-Pastur law. This is a joint work with Indrajit Jana.

Speaker: Alexander Soshnikov , UC Davis
Location:
Fine Hall 214
April 12, 2017
3:00pm - 4:00pm
Rates in randomized CLTs for weighted sums of dependent summands

We will discuss a second order concentration phenomenon on the sphere, and its applications to the normal approximation for weighted sums of not necessarily independent random variables.

Speaker: Sergey Bobkov , university of Minnesota
Location:
Fine Hall 214