658 citations · 2.2k across the 187 of their papers we have counts for
87 papers · 1 filter
Consensus times for monotone aggregation dynamics
Elchanan Mossel
We study an asynchronous consensus dynamics on agents: at each step a uniformly chosen agent replaces its state by , where is a fixed monotone aggregation…
Sharp Threshold for the Convergence of Nonstationary Averaging
Saba Lepsveridze, Elchanan Mossel
We study non-stationary averaging processes, where each term of a sequence is a weighted average of previous terms, namely . Our results extend c…
Reconstructing Riemannian Metrics From Random Geometric Graphs
Han Huang, Pakawut Jiradilok, Elchanan Mossel
Random geometric graphs are random graph models defined on metric measure spaces. A random geometric graph is generated by first sampling points from a metric space and then connec…
On Algorithmic Robustness of Corrupted Markov Chains
Jason Gaitonde, Elchanan Mossel
We study the algorithmic robustness of general finite Markov chains in terms of their stationary distributions to general, adversarial corruptions of the transition matrix. We show…
Asymptotics for the harmonic descent chain and applications to critical beta-splitting trees
Anna Brandenberger, Byron Chin, Elchanan Mossel
Motivated by the connection to a probabilistic model of phylogenetic trees introduced by Aldous, we study the recursive sequence governed by the rule $x_n = \sum_{i=1}^{n-1} \frac{…
Stochastic block models with many communities and the Kesten--Stigum bound
Byron Chin, Elchanan Mossel, Youngtak Sohn +1
We study the inference of communities in stochastic block models with a growing number of communities. For block models with vertices and a fixed number of communities , it…
Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions
Rupert Li, Elchanan Mossel
Recent works explore deep learning's success by examining functions or data with hierarchical structure. To study the learning complexity of functions with hierarchical structure,…
Optimal Low degree hardness for Broadcasting on Trees
Han Huang, Elchanan Mossel
Broadcasting on trees is a fundamental model from statistical physics that plays an important role in information theory, noisy computation and phylogenetic reconstruction within c…
Random Subwords and Billiard Walks in Affine Weyl Groups
Colin Defant, Pakawut Jiradilok, Elchanan Mossel
Let be an irreducible affine Weyl group, and let be a finite word over the alphabet of simple reflections of . Fix a probability . For each integer $…
Finding the root in random nearest neighbor trees
Anna Brandenberger, Cassandra Marcussen, Elchanan Mossel +1
We study the inference of network archaeology in growing random geometric graphs. We consider the root finding problem for a random nearest neighbor tree in dimension $d \in \mathb…
Comparison Theorems for the Mixing Times of Systematic and Random Scan Dynamics
Jason Gaitonde, Elchanan Mossel
A popular method for sampling from high-dimensional distributions is the \emph{Gibbs sampler}, which iteratively resamples sites from the conditional distribution of the desired me…
Multiplayer Games of War
Axel Adjei, Neil Krishnan, Elchanan Mossel
A recent paper by Bhatia, Chin, Mani, and Mossel (2026) defined stochastic processes modeling the game of War for {\em two players} with cards. That paper showed that these mod…
Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs
Elchanan Mossel, Allan Sly, Youngtak Sohn
The stochastic block model is a canonical model of communities in random graphs. It was introduced in the social sciences and statistics as a model of communities, and in theoretic…
Monotonicity, Topology, and Convexity of Recurrence in Random Walks
Rupert Li, Elchanan Mossel, Benjamin Weiss
We consider non-homogeneous random walks on the two-dimensional positive quadrant and the one-dimensional slab . In the 1960's the f…
Low Degree Hardness for Broadcasting on Trees
Han Huang, Elchanan Mossel
We study the low-degree hardness of broadcasting on trees. Broadcasting on trees has been extensively studied in statistical physics, in computational biology in relation to phylog…
Stable matchings with correlated Preferences
Christopher Hoffman, Avi Levy, Elchanan Mossel
The stable matching problem has been the subject of intense theoretical and empirical study since the seminal 1962 paper by Gale and Shapley. The number of stable matchings for dif…
Influences in Mixing Measures
Frederic Koehler, Noam Lifshitz, Dor Minzer +1
The theory of influences in product measures has profound applications in theoretical computer science, combinatorics, and discrete probability. This deep theory is intimately conn…
The Power of an Adversary in Glauber Dynamics
Byron Chin, Ankur Moitra, Elchanan Mossel +1
Glauber dynamics are a natural model of dynamics of dependent systems. While originally introduced in statistical physics, they have found important applications in the study of so…
Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees
Elchanan Mossel, Allan Sly, Youngtak Sohn
In this paper we continue to rigorously establish the predictions in ground breaking work in statistical physics by Decelle, Krzakala, Moore, Zdeborová (2011) regarding the block m…
Reconstruction on Trees and Low-Degree Polynomials
Frederic Koehler, Elchanan Mossel
The study of Markov processes and broadcasting on trees has deep connections to a variety of areas including statistical physics, graphical models, phylogenetic reconstruction, Mar…
Spectral Recovery of Binary Censored Block Models
Souvik Dhara, Julia Gaudio, Elchanan Mossel +1
Community detection is the problem of identifying community structure in graphs. Often the graph is modeled as a sample from the Stochastic Block Model, in which each vertex belong…
Probabilistic Aspects of Voting, Intransitivity and Manipulation
Elchanan Mossel
These lecture notes are based on lectures given in 2019 Saint-Flour Probability School.
Shotgun Assembly of Erdos-Renyi Random Graphs
Julia Gaudio, Elchanan Mossel
Graph shotgun assembly refers to the problem of reconstructing a graph from a collection of local neighborhoods. In this paper, we consider shotgun assembly of \ER random graphs $G…
Broadcasting on Two-Dimensional Regular Grids
Anuran Makur, Elchanan Mossel, Yury Polyanskiy
We study a specialization of the problem of broadcasting on directed acyclic graphs, namely, broadcasting on 2D regular grids. Consider a 2D regular grid with source vertex at…