Virtual

In recent years a fruitful interplay has been unfolding between quantum chaos and black holes. In the first part of the talk, I provide a sampler of these developments. Next, we study the fate of the black hole interior at late times in simple models of quantum gravity that have dual descriptions in terms of Random Matrix Theory. We find that the volume of the interior grows linearly at early times and then, due to non-perturbative effects, saturates at a time and towards a value that are exponentially large in the entropy of the black hole. This provides a confirmation of the complexity equals volume proposal of Susskind, since in chaotic systems complexity is also expected to exhibit the same behavior.

We study sampling from a target distribution $e^{-f}$ using the unadjusted Langevin Monte Carlo (LMC) algorithm. For any potential function $f$ whose tails behave like $\|x\|^\alpha$ for $\alpha \in [1,2]$, and has $\beta$-H\"older continuous gradient, we derive the sufficient number of steps to reach the $\epsilon$-neighborhood of a $d$-dimensional target distribution as a function of $\alpha$ and $\beta$. Our rate estimate, in terms of $\epsilon$ dependency, is not directly influenced by the tail growth rate $\alpha$ of the potential function as long as its growth is at least linear, and it only relies on the order of smoothness $\beta$.

Our rate recovers the best known rate which was established for strongly convex potentials with Lipschitz gradient in terms of $\epsilon$ dependency, but we show that the same rate is achievable for a wider class of potentials that are degenerately convex at infinity.

The success of operator splitting techniques for convex optimization has led to an explosion of methods for solving large-scale and non convex optimization problems via convex relaxation. 

This success is at the cost of overlooking direct approaches to operator splitting that embrace some of the more inconvenient aspects of many model problems, namely nonconvexity, non smoothness and infeasibility.  I will introduce some of the tools we have developed for handling these issues, and present sketches of the basic results we can obtain.

The formalism is in general metric spaces, but most applications have their basis in Euclidean spaces.  Along the way I will try to point out connections to other areas of intense interest, such as optimal mass transport.

The aim of this talk is to understand the qualitative properties that emerge from a PDE model inspired from neurosciences, in order to understand what are the key processes that lead to mathematical complex patterns for the solutions of this equation. 

This talk will be about the stable boundary seen from different recent points of view.

Randomized NLA methods have recently gained popularity because of their easy implementation, computational efficiency, and numerical robustness. We propose a randomized version of a well-established FEAST eigenvalue algorithm that enables computing the eigenvalues of the Hermitian matrix pencil $(\textbf{A},\textbf{B})$ located in the given real interval $\mathcal{I} \subset [\lambda_{min}, \lambda_{max}]$. In this talk, we will present deterministic as well as probabilistic error analysis of the accuracy of approximate eigenpair and subspaces obtained using the randomized FEAST algorithm. First, we derive bounds for the canonical angles between the exact and the approximate eigenspaces corresponding to the eigenvalues contained in the interval $\mathcal{I}$. Then, we present bounds for the accuracy of the eigenvalues and the corresponding eigenvectors. This part of the analysis is independent of the particular distribution of an initial subspace, therefore we denote it as deterministic. In the case of the starting guess being a Gaussian random matrix, we provide more informative, probabilistic error bounds. Finally, we will illustrate numerically the effectiveness of all the proposed error bounds.

---

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact @email.

We introduce a new method for studying stochastic processes in random graphs controlled by degree information, involving combining enumeration techniques with an abstract second moment argument. We use it to constructively resolve a conjecture of Füredi from 1988: with high probability, the random graph G(n,1/2) admits a friendly bisection of its vertex set, i.e., a partition of its vertex set into two parts whose sizes differ by at most one in which n-o(n) vertices have at least as many neighbours in their own part as across. This work is joint with Asaf Ferber, Matthew Kwan, Bhargav Narayanan, and Mehtaab Sawhney.

We study a family of evolving directed random graphs that includes the directed preferential model and the directed uniform attachment model. The directed preferential model is of particular interest since it is known to produce scale-free graphs with regularly varying in-degree distribution. We start by describing the local weak limits for our family of random graphs in terms of randomly stopped continuous-time branching processes, and then use these limits to establish the asymptotic behavior of the corresponding PageRank distribution. We show that the limiting PageRank distribution decays as a power-law in both models, which is surprising for the uniform attachment model where the in-degree distribution has exponential tails. And even for the preferential attachment model, where the power-law hypothesis suggests that PageRank should follow a power-law, our result shows that the two tail indexes are different, with the PageRank distribution having a heavier tail than the in-degree distribution.

Suppose there are $n$ students in a class. But assume that not everybody is friends with everyone else, and there is a graph which determines the friendship structure. What is the chance that there are two friends in this class, both with birthdays on October 12? More generally, given a simple labelled graph $G_n$ on $n$ vertices, color each vertex with one of $c=c_n$ colors chosen uniformly at random, independent from other vertices. We study the question: what is the number of monochromatic edges of color 1?

As it turns out, the limiting distribution has three parts, the first and second of which are quadratic and linear functions of a homogeneous Poisson point process, and the third component is an independent Poisson. In fact, we show that any distribution limit must belong to the closure of this class of random variables. As an application, we characterize exactly when the limiting distribution is a Poisson random variable.

This talk is based on joint work with Bhaswar Bhattacharya and Somabha Mukherjee.