# Seminars & Events for Probability Seminar

##### 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.

##### 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.

##### 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.

##### 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.

##### 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.

##### 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.

##### 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.

##### 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.

##### 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.

##### 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)

##### 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.

##### 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.

##### 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.

##### 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.

##### 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.