Probability and Mathematical Physics Seminar

Synopsis:

In this talk, we will focus on the planted clique model, denoted by G(n,1/2,k), which is originally introduced by Jerrum in 1992. An instance of G(n,1/2,k) is generated by planting a clique of size k uniformly at random in a vanilla Erdős-Rényi graph G(n,1/2). The inference goal is to recover the vertices of the planted clique from an instance of G(n,1/2,k). The study of the model have been the focus of a large line of work arising from the probability theory, computer science and statistics communities. While we know that as long as k > (2+\epsilon) log_2(n), for some \epsilon > 0, the clique is recoverable via brute-force methods, no polynomial-time method is proven to succeed unless k > c \sqrt{n} for some c > 0. A convincing explanation for the failure of polynomial-time methods in the regime where k is much smaller than \sqrt{n} is currently missing in the literature of the model.

We are going to discuss some new results on the geometry of the dense subgraphs in an instance of G(n,1/2,k). Our results suggest that k = Θ (\sqrt{n}) admits an explanation as the phase transition point for the presence of a certain Overlap Gap Property (OGP) on the space of dense subgraphs. OGP is a disconnectivity notion which originates in spin glass theory and is known to suggest algorithmic harness when it appears. Finally, we show that OGP implies the failure of a large family of MCMC methods to recover the clique when k is much smaller than \sqrt{n}.

This is joint work with David Gamarnik.

Event Details Page

Synopsis:

I will describe recent work regarding the structure of and random walks on the two- and three-dimensional uniform spanning trees. The results from the two-dimensional case are from joint works with Martin Barlow (UBC) and Takashi Kumagai (Kyoto), and as well as a scaling limit, include demonstrating fluctuations in the on-diagonal part of the quenched heat kernel, and off-diagonal estimates for the averaged heat kernel. As for the three-dimensional situation, this is being investigated in an ongoing work with Omer Angel (UBC), Sarai Hernandez-Torres (UBC) and Daisuke Shiraishi (Kyoto). In the latter work, we demonstrate the tightness of the graph and the random walk's annealed law under rescaling, and convergence along a particular subsequence.  We also derive the random walk's walk dimension (with respect to both the intrinsic and Euclidean metric) and its spectral dimension, as well as heat kernel estimates for any diffusion that arises as a scaling limit.

Event Details Page

Synopsis:

TBA

Event Details Page

Synopsis:

Liouville theory is a fundamental example of a conformal field theory (CFT) first introduced by A. Polyakov in the context of string theory. In recent years it has been rigorously studied using probabilistic techniques. In this talk we will present a probabilistic construction of the conformal blocks of Liouville CFT on the torus. These are the fundamental objects that allow to understand the integrable structure of CFT using the conformal bootstrap equation. We will also mention the connection with the AGT correspondence. Based on joint work with Promit Ghosal, Xin Sun, and Yi Sun.

Event Details Page

Synopsis:

TBA

Event Details Page

Synopsis:

TBA

Event Details Page

Event Details Page

Event Details Page

Event Details Page

Event Details Page

Event Details Page

Synopsis:

TBA

Event Details Page

Synopsis:

I discuss entanglement entropy of bipartite systems using the von Neumann entropy as measure of entanglement. Some of the most widely studied systems include one-dimensional quantum critical systems, such as quantum spin chains, which in their simplest setting consist of $N$ spins. Of particular interest is the XX spin chain model with zero magnetic field and the study of the von Neumann entropy of the subsystem $P$ of spins on lattice sites $\{1,2,\dots,m\}\cup\{2m+1,2m+2,\dots, 3m\}$, which can be analyzed using certain integral representations. For a single block subsystem, the integral representation involves Toeplitz determinants and the entropy can be calculated using the Fisher-Hartwig asymptotic expansion of these determinants. In this talk, we consider a subsystem that consists of two blocks of spins separated by one spin and compute the mutual information between the two intervals explicitly and rigorously using the Riemann-Hilbert approach. Joint work with György Gehér (Reading University) and Alexander Its (Indiana University-Purdue University Indianapolis).

Event Details Page

Synopsis:

Event Details Page

Synopsis:

Let X be a random variable taking values in {0,...,n} and f(z) be its probability generating function.  Pemantle conjectured that if the variance of X is large and f has no roots close to 1 in the complex plane, then X must be approximately normal. We will discuss a complete resolution of this conjecture in a strong quantitative form, thereby giving the best possible version of a result of Lebowitz, Pittel, Ruelle and Speer. Additionally, if f has no roots with small argument, then X must be approximately normal, again in a sharp quantitative form. These results also imply a multivariate central limit theorem that answers a conjecture and completes a program of Ghosh, Liggett and Pemantle.  This talk is based on joint work with Julian Sahasrabudhe.

Event Details Page