The seminar is jointly sponsored by Temple and Penn. The organizers are Brian Rider and Atilla Yilmaz (Temple), and Jian Ding and Robin Pemantle (Penn).
Talks are Tuesdays 3:00 - 4:00 pm and are held either in Wachman Hall (Temple) or David Rittenhouse Lab (Penn) as indicated below.
For a chronological listing of the talks, click the year above.
Pascal Maillard, Orsay/CRM
I will report on recent work with Louigi Addario-Berry on algorithmic hardness for finding low-energy states in the continuous random energy model of Bovier and Kurkova. This model can be regarded as a toy model for strongly correlated random energy landscapes such as the Sherrington-Kirkpatrick model. We exhibit a precise and explicit hardness threshold: finding states of energy above the threshold can be done in linear time, while below the threshold this takes exponential time for any algorithm with high probability. I further discuss what insights this yields for understanding algorithmic hardness thresholds for random instances of combinatorial optimization problems.
Sunder Sethuraman, University of Arizona
A GEM (Griffiths-Engen-McCloskey) sequence specifies the (random) proportions in splitting a `resource' infinitely many ways. Such sequences form the backbone of `stick breaking' representations of Dirichlet processes used in nonparametric Bayesian statistics. In this talk, we consider the connections between a class of generalized `stick breaking' processes, an intermediate structure via `clumped' GEM sequences, and the occupation laws of certain time-inhomogeneous Markov chains.
Abram Magner, Purdue University
Networks in the real world are dynamic -- nodes and edges are added and removed over time, and time-varying processes (such as epidemics) run on them. In this talk, I will describe mathematical aspects of some of my recent work with collaborators on statistical inference and compression problems that involve this time-varying aspect of networks. I will focus on two related lines of work: (i) network archaeology -- broadly concerning problems of dynamic graph model validation and inference about previous states of a network given a snapshot of its current state, and (ii) structural compression -- for a given graph model, exhibit an efficient algorithm for invertibly mapping network structures (i.e., graph isomorphism types) to bit strings of minimum expected length. For both classes of problems, I give both information-theoretic limits and efficient algorithms for achieving those limits. Finally, I briefly describe some ongoing projects that continue these lines of work.
Philippe Sosoe, Cornell University
I will explain how two recent technical developments in Random Matrix Theory allow for a precise description of the fluctuations of single eigenvalues in the spectrum of large symmetric matrices. No prior knowledge of random matrix theory will be assumed. (Based on joint work with B. Landon and H.-T. Yau.)
Anirban Basak, Tata Institute
Consider an $n \times n$ matrix with i.i.d. Bernoulli($p$) entries. It is well known that for $p= \Omega(1)$, i.e., $p$ bounded below by some positive constant, the matrix is invertible with high probability. If $p \ll \frac{\log n}{n}$ then the matrix contains zero rows and columns with high probability and hence it is singular with high probability. In this talk, we will discuss the sharp transition of the invertibility of this matrix at $p =\frac{\log n}{n}$. This phenomenon extends to the adjacency matrices of directed and undirected Erdös-Rényi graphs, and random bipartite graphs. Joint work with Mark Rudelson.
Julian Gold, Northwestern University
We study the isoperimetric subgraphs of the infinite cluster $\textbf{C}_\infty$ of supercritical bond percolation on $\mathbb{Z}^d$, $d \geq 3$. We prove a shape theorem for these random graphs, showing that upon rescaling they tend almost surely to a deterministic shape. This limit shape is itself an isoperimetric set for a norm we construct. In addition, we obtain sharp asymptotics for a modification of the Cheeger constant of $\textbf{C}_\infty \cap [-n,n]^d$, settling a conjecture of Benjamini for this modified Cheeger constant. Analogous results are shown for the giant component in dimension two, where we use the original definition of the Cheeger constant, and a more complicated continuum isoperimetric problem emerges as a result.
Janos Englander, CU Boulder
Given a sequence of numbers $p_n ∈ [0, 1]$, consider the following experiment. First, we flip a fair coin and then, at step $n$, we turn the coin over to the other side with probability $p_n, n > 1$, independently of the sequence of the previous terms. What can we say about the distribution of the empirical frequency of heads as $n \to \infty$? We show that a number of phase transitions take place as the turning gets slower (i.e. $p_n$ is getting smaller), leading first to the breakdown of the Central Limit Theorem and then to that of the Law of Large Numbers. It turns out that the critical regime is $p_n = \textrm{const}/n$. Among the scaling limits, we obtain Uniform, Gaussian, Semicircle and Arcsine laws. The critical regime is particularly interesting: when the corresponding random walk is considered, an interesting process emerges as the scaling limit; also, a connection with Polya urns will be mentioned. This is joint work with S. Volkov (Lund) and Z. Wang (Boulder).
Firas Rassoul-Agha, University of Utah
We study standard first-passage percolation via related optimization problems that restrict path length. The path length variable is in duality with a shift of the weights. This puts into a convex duality framework old observations about the convergence of geodesic length due to Hammersley, Smythe and Wierman, and Kesten. We study the regularity of the time constant as a function of the shift of weights. For unbounded weights, this function is strictly concave and in case of two or more atoms it has a dense set of singularities. For any weight distribution with an atom at the origin there is a singularity at zero, generalizing a result of Steele and Zhang for Bernoulli FPP. The regularity results are proved by the van den Berg-Kesten modification argument. This is joint work with Arjun Krishnan and Timo Seppäläinen.
Julian Sahasrabudhe, Cambridge University
While it is an old and fundamental fact that every (nice enough) even function $f : [-\pi,\pi] \rightarrow \mathbb{C}$ may be uniquely expressed as a cosine series \[ f(\theta) = \sum_{r \geq 0 } C_r\cos(r\theta), \] the relationship between the sequence of coefficients $(C_r)_{r \geq 0 }$ and the behavior of the function $f$ remains mysterious in many aspects. We mention two variations on this theme. First a more probabilistic setting: what can be said about a random variable if we constrain the roots of the probability generating function? We then settle on our main topic; a solution to a problem of J.E. Littlewood about the behavior of the zeros of cosine polynomials with coefficients $C_r \in \{0,1\}$.
Arjun Krishnan, University of Rochester
Consider a measurable dense family of semi-infinite nearest-neighbor paths on the integer lattice in d dimensions. If the measure on the paths is translation invariant, we completely classify their collective behavior in d=2 under mild assumptions. We use our theory to classify the behavior of semi-infinite geodesics in random translation invariant metrics on the lattice; it applies, in particular, to first- and last-passage percolation. We also construct several examples displaying unexpected behaviors. (Joint work with Jon Chaika.)
Thomas Leblé, NYU Courant
One-dimensional log-gases, or Beta-ensembles, are statistical physics toy models finding their incarnation in random matrix theory. Their limit behavior at microscopic scale is known as the Sine-beta process, its original description involves systems of coupled SDE’s.
We give a new description of Sine-beta as an « infinite volume Gibbs measure », using the Dobrushin-Lanford-Ruelle (DLR) formalism, and use it to prove the “rigidity” of the process, in the sense of Ghosh-Peres. If time permits, I will mention another application to the study of fluctuations of linear statistics. Joint work with David Dereudre, Adrien Hardy, and Mylène Maïda.
Swee Hong Chen, Cornell
How much randomness is needed to prove a scaling limit result? In this talk we consider this question for a family of random walks on the square lattice. When the randomness is turned to the maximum, we have the symmetric random walk, which is known to scale to a two-dimensional Brownian motion. When the randomness is turned to zero, we have the rotor walk, for which its scaling limit is an open problem. This talk is about random walks that lie in between these two extreme cases and for which we can prove their scaling limit. This is a joint work with Lila Greco, Lionel Levine, and Boyao Li.