I am co-organizing a virtual Probability Seminar with Wei-Kuo Chen and Arnab Sen at University of Minnesota for
the Fall 2023 semester. Please email me to get the Zoom link for the seminar series.
The seminar is held on Fridays at 2:30pm (ET), unless otherwise noted below.
| 09/22/2023 | Eren C. Kızıldağ (Columbia U) |
| Title: Algorithmic Barriers from Intricate Geometry in Random Optimization Problems. | |
| Abstract: Random optimization problems are central in the study of random structures, including spin glasses and random graphs. These problems often exhibit a statistical-computational gap: the best known efficient algorithm finds a strictly suboptimal solution and no better algorithm is known. In this talk, we study the limits of efficient algorithms for certain such problems. Our first focus is on the symmetric binary perceptron (SBP) model, a random constraint satisfaction problem which is closely related to discrepancy minimization. We prove that the solution space of the SBP exhibits intricate geometrical features, known as the multi Overlap Gap Property (m-OGP). By leveraging m-OGP, we obtain nearly sharp hardness guarantees against the classes of stable algorithms and online algorithms. These classes capture many of the best known algorithms for the SBP and related models. Our results yield the first nearly tight unconditional lower bounds in the online setting. We then extend the same program to other models, including discrepancy minimization and random number balancing. Time permitting, I will also discuss how the same program extends to planted models. Based on joint works [1, 2, 3] with David Gamarnik, Will Perkins, and Changji Xu. | |
| 09/29/2023 | Julia Gaudio (Northwestern) |
| Title: Average-case and smoothed analysis of graph isomorphism. | |
| Abstract: We propose a simple and efficient local algorithm for graph isomorphism which succeeds for a large class of sparse graphs. This algorithm produces a low-depth canonical labeling, which is a labeling of the vertices of the graph that identifies its isomorphism class using vertices' local neighborhoods. Prior work by Czajka and Pandurangan showed that the degree profile of a vertex (i.e., the sorted list of the degrees of its neighbors) gives a canonical labeling with high probability when npn= ω(log4(n)/loglog n) (and pn ≤ 1/2); subsequently, Mossel and Ross showed that the same holds when npn= ω(log2(n)). We first show that their analysis essentially cannot be improved: we prove that when npn = o(log2(n)/(loglog n)3), with high probability there exist distinct vertices with isomorphic 2-neighborhoods. Our first main result is a positive counterpart to this, showing that 3-neighborhoods give a canonical labeling when npn≥ (1+δ) log n (and pn ≤ 1/2); this improves a recent result of Ding, Ma, Wu, and Xu, completing the picture above the connectivity threshold. Our second main result is a smoothed analysis of graph isomorphism, showing that for a large class of deterministic graphs, a small random perturbation ensures that 3-neighborhoods give a canonical labeling with high probability. While the worst-case complexity of graph isomorphism is still unknown, this shows that graph isomorphism has polynomial smoothed complexity. Joint work with Miklós Rácz and Anirudh Sridhar | |
| 10/06/2023 | Yinon Spinka (Tel Aviv) |
| Title: Characterizing (non)amenability through stochastic domination and finitary codings. | |
| Abstract: Consider the plus state of the Ising model at very low temperature on some graph. Does it stochastically dominate a high-density Bernoulli percolation? The answer depends drastically on the geometry of the graph. We'll discuss this and other questions of stochastic domination, and how amenability or lack thereof plays a crucial role. A process is a finitary factor of iid if it can be written as a measurable and equivariant function of an iid process. Van den Berg and Steif showed that the plus state of the Ising model on an amenable graph is a finitary factor of iid if and only if it coincides with the minus state. In sharp contrast, we show that it is a finitary factor of iid at very low temperatures on a nonamenable graph. Joint work with Gourab Ray. | |
| 10/20/2023 | Tom Hutchcroft (Caltech) |
| Title: Percolation on Finite Transitive Graphs. | |
| Abstract: I will describe recent work developing a general theory of percolation on arbitrary finite transitive graphs, summarising our progress on the basic questions: When is there a phase transition for the emergence of a giant cluster? When is the giant cluster unique? How does this relate to percolation on infinite graphs? While the answers to these questions are classical in several well-studied examples such as tori, complete graphs, hypercubes, expanders, and so on, we will see that a surprisingly general and complete answer to each of these questions is possible starting only with the assumption of transitivity. Joint work with Philip Easo. | |
| 10/27/2023 | Promit Ghosal (Brandeis U) |
| Title: Fractal Geometry of the Parabolic Anderson Model in higher dimension. | |
| Abstract: Parabolic Anderson model (PAM) is one of the prototypical frameworks for modelling conduction of electrons in crystals filled with defects. Intermittency of the peaks of the PAM is one of the widely studied topics in the last few decades and it holds close ties with the phenomenon of Anderson localization. We show that the peaks of the PAM in dimension 2 and 3 are macroscopically multifractal. More precisely, we prove that the spatial peaks of the PAM have infinitely many distinct values and we compute the macroscopic Hausdorff dimension (introduced by Barlow and Taylor) of those peaks. As a byproduct, we obtain the exact spatial asymptotics of the solution of the PAM. We also study the spatio-temporal peaks of the PAM and show their macroscopic multifractality. Some of the major tools used in our proof techniques include paracontrolled calculus and tail probabilities of the largest point in the spectrum of the Anderson Hamiltonian. This talk is based on a joint work with Jaeyun Yi. | |
| 11/03/2023 | Elizabeth Collins-Woodfin (McGill) |
| Title: Bipartite spherical spin glass at critical temperature (with a random matrix detour). | |
| Abstract: One of the fascinating phenomena of spin glasses is the dramatic change in behavior that occurs between the high and low temperature regimes. The free energy of the spherical Sherrington-Kirkpatrick (SSK) model, for example, has Gaussian fluctuations at high temperature, but Tracy-Widom fluctuations at low temperature. A similar phenomenon holds for the bipartite SSK model, and we show that, when the temperature is within a small window around the critical temperature, the free energy fluctuations converge to an independent sum of Gaussian and Tracy-Widom random variables (joint work with Han Le). Our work follows two recent papers that proved similar results for the SSK model (by Landon and by Johnstone, Klochkov, Onatski, Pavlyshyn). Analyzing bipartite SSK at critical temperature requires a variety of tools including classical random matrix results, contour integral techniques, and a CLT for the log-characteristic polynomial of Laguerre (Wishart) random matrices evaluated near the spectral edge. This last ingredient was not present in the literature when we began our project, so I will discuss our proof of this CLT, which has other applications separate from bipartite spin glasses. | |
| 11/10/2023 | Mark Sellke (Harvard) |
| Title: The Threshold Energy of Low Temperature Langevin Dynamics for Pure Spherical Spin Glasses. | |
| Abstract: We study the Langevin dynamics for spherical p-spin models, focusing on the short time regime described by the Cugliandolo-Kurchan equations. Confirming a 1999 conjecture of Biroli, we show the asymptotic energy achieved is exactly \(\small 2\sqrt{(p-1)/p}\) in the low temperature limit. The upper bound uses hardness results for Lipschitz optimization algorithms and applies for all temperatures. For the lower bound, we prove the dynamics reaches and stays above the lowest energy of any approximate local maximum. In fact the latter behavior holds for any Hamiltonian obeying natural smoothness estimates, even with disorder-dependent initialization and on exponential time-scales. Time permitting, I will also explain why these ideas imply fast mixing of low temperature Langevin dynamics for "topologically trivial" spin glasses. | |
| 11/17/2023 | Zoe Huang (UNC) |
| Title: Co-evolving dynamic networks. | |
| Abstract: Co-evolving network models, wherein dynamics such as random walks on the network influence the evolution of the network structure, which in turn influences the dynamics, are of interest in a range of domains. While much of the literature in this area is currently supported by numerics, providing evidence for fascinating conjectures and phase transitions, proving rigorous results has been quite challenging. The two aims of this talk are: (i) Propose a general class of co-evolving network models driven by local exploration, started from a single vertex called the root. New vertices enter the system, explore the current network via randomly sampling a vertex and then exploring the graph for a random number of steps in the direction of the root. Specific choices of the exploration step distribution lead to preferential attachment with global attachment functionals such as PageRank scores. We show that the model shows non-trivial phase transition phenomena, including condensation of a fixed density of edges about the root, as well as phase transitions of functionals such as the PageRank distribution. (ii) Develop mathematical machinery for the rigorous analysis of such models, including local weak convergence, infinite dimensional urn models, related multi-type branching processes and corresponding Perron-Frobenius theory, branching random walks, and in particular relating tail exponents of various functionals to the scaling exponents of quasi-stationary distributions of associated random walks. (Based on joint work with Sayan Banerjee and Shankar Bhamidi.) | |
| 12/01/2023 | Ilias Zadik (Yale) |
| Title: Sharp thresholds imply circuit lower bounds: From random 2-SAT to planted clique | |
| Abstract: In this talk, we will present a recent result that if a Boolean function exhibits a sharp threshold at an arbitrary density then it immediately implies a bounded depth circuit lower bounds for computing this function on average. By leveraging the rich literature of sharp thresholds, this method implies multiple new average-case circuit lower bounds. Time permitted, we will discuss new AC0 lower bounds for the random 2-SAT problem at the satisfiability threshold, the k-clique decision problem in random graphs, and also the planted clique model from the literature of statistical estimation. Joint work with David Gamarnik and Elchanan Mossel. | |
| 12/08/2023 | Corrine Yap (Georgia Tech) |
| Title: Reconstructing Random Pictures. | |
| Abstract: Reconstruction problems ask whether or not it is possible to uniquely build a discrete structure from the collection of its substructures of a fixed size. This question has been explored in a wide range of settings, most famously with graphs and the resulting Graph Reconstruction Conjecture due to Kelly and Ulam, but also including geometric sets, jigsaws, and abelian groups. In this talk, we'll consider the reconstruction of random pictures (n-by-n grids with binary entries) from the collection of its k-by-k subgrids and prove a nearly-sharp threshold for k = k(n). Our main proof technique is an adaptation of the Peierls contour method from statistical physics. Joint work with Bhargav Narayanan. | |