658 citations · 2.2k across the 187 of their papers we have counts for
13 papers · 1 filter
Broadcasting on Random Directed Acyclic Graphs
Anuran Makur, Elchanan Mossel, Yury Polyanskiy
We study a generalization of the well-known model of broadcasting on trees. Consider a directed acyclic graph (DAG) with a unique source vertex , and suppose all other vertices…
How Many Subpopulations is Too Many? Exponential Lower Bounds for Inferring Population Histories
Younhun Kim, Frederic Koehler, Ankur Moitra +2
Reconstruction of population histories is a central problem in population genetics. Existing coalescent-based methods, like the seminal work of Li and Durbin (Nature, 2011), attemp…
Long ties accelerate noisy threshold-based contagions
Dean Eckles, Elchanan Mossel, M. Amin Rahimian +1
Network structure can affect when and how widely new ideas, products, and behaviors are adopted. In widely-used models of biological contagion, interventions that randomly rewire e…
Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard
Jan Hązła, Ali Jadbabaie, Elchanan Mossel +1
We study the Bayesian model of opinion exchange of fully rational agents arranged on a network. In this model, the agents receive private signals that are indicative of an unkown s…
Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't
Yan Jin, Elchanan Mossel, Govind Ramnarayan
We consider a variation of the problem of corruption detection on networks posed by Alon, Mossel, and Pemantle '15. In this model, each vertex of a graph can be either truthful or…
Seeded Graph Matching via Large Neighborhood Statistics
Elchanan Mossel, Jiaming Xu
We study a well known noisy model of the graph isomorphism problem. In this model, the goal is to perfectly recover the vertex correspondence between two edge-correlated Erdős-Rény…
Contextual Stochastic Block Models
Yash Deshpande, Andrea Montanari, Elchanan Mossel +1
We provide the first information theoretic tight analysis for inference of latent community structure given a sparse graph along with high dimensional node covariates, correlated w…
Is your function low-dimensional?
Anindya De, Elchanan Mossel, Joe Neeman
We study the problem of testing if a function depends on a small number of linear directions of its input data. We call a function a linear -junta if it is completely determ…
Learning Restricted Boltzmann Machines via Influence Maximization
Guy Bresler, Frederic Koehler, Ankur Moitra +1
Graphical models are a rich language for describing high-dimensional distributions in terms of their dependence structure. While there are algorithms with provable guarantees for l…
The Probability of Intransitivity in Dice and Close Elections
Jan Hązła, Elchanan Mossel, Nathan Ross +1
We study the phenomenon of intransitivity in models of dice and voting. First, we follow a recent thread of research for -sided dice with pairwise ordering induced by the probab…
Broadcasting on Bounded Degree DAGs
Anuran Makur, Elchanan Mossel, Yury Polyanskiy
We study the following generalization of the well-known model of broadcasting on trees. Consider an infinite directed acyclic graph (DAG) with a unique source node . Let the col…
The Vertex Sample Complexity of Free Energy is Polynomial
Vishesh Jain, Frederic Koehler, Elchanan Mossel
We study the following question: given a massive Markov random field on nodes, can a small sample from it provide a rough approximation to the free energy $\mathcal{F}_n = \log…
The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity
Vishesh Jain, Frederic Koehler, Elchanan Mossel
The mean field approximation to the Ising model is a canonical variational tool that is used for analysis and inference in Ising models. We provide a simple and optimal bound for t…