Probability
Organizers: Amir Dembo (Autumn, Winter) & Eric Thoma (Spring)
Upcoming Events
Spin models on graphs are a source of many interesting questions in statistical physics, algorithms, and combinatorics. The Ising model is a classical example: first introduced as a model of magnetization, it can combinatorially be described as a weighted probability distribution on two-vertex…
Past Events
Last passage percolation (LPP) is a model of random geometry where the main observable is a directed path evolving in a random environment. When the environment distribution has light tails and a fast decay of correlation, the random fluctuations of LPP are predicted to be explained by the…
Fundamentals of statistical mechanics explain that systems in thermal equilibrium spend a greater fraction of their time in states with apparent order because these states have lower energy. This explanation is remarkable, and powerful, because energy is a "local" property of states. While non-…
Strongly correlated particle systems, such as Coulomb gases and zeros of Gaussian polynomials, have been shown in recent years to display a wide range of behavior vis-a-vis their spatial laws. In particular, their local distributions under spatial conditioning are often characterized by…
The Burnside process is a general Markov chain for sampling unlabeled objects. Two examples of the Burnside process give new algorithms for uniformly sampling contingency tables and integer partitions. Both these algorithms have "lumped" versions. These lumped processes are also Markov chains,…
The stochastic block model (SBM), a random graph generalizing the Erdős–Rényi model, has long served as a framework for community detection. For SBMs with $n$ vertices and a fixed number of communities $q$, Decelle et al. (2011) predicted that efficient recovery is possible above the Kesten–…
The stochastic block model is a canonical model of communities in random graphs. Given a sparse stochastic block model, the two standard inference tasks are:
- Weak recovery: Can we estimate the communities with non-trivial overlap with the true communities?
- Detection/hypothesis…
We show new lower bounds for sphere packings in high dimensions and for independent sets in graphs with not-too-large co-degrees. For dimension d, this achieves a sphere packing of density (1 + o(1)) d log d / 2^(d+1). In general dimension this provides the first asymptotically growing…
I will discuss large deviation principles for the right-most eigenvalue of Wigner matrices with sub-Gaussian entries. Previous work of Guionnet and Husson established a universal rate function for the light-tailed "sharp sub-Gaussian" case, where large deviations result from "delocalized"…
Understanding the generalization properties of large, overparametrized, neural networks is a central problem in theoretical machine learning. Several insightful ideas have been proposed in this regard, among them: the implicit bias hypothesis, the possibility of having benign overfitting and the…
I shall discuss first-passage percolation on Cayley graphs of Gromov hyperbolic groups under mild conditions on the passage time distribution. Appealing to deep geometric and topological facts about hyperbolic groups and their boundaries, several questions become more tractable in this set-up…