658 citations · 2.2k across the 187 of their papers we have counts for
11 papers · 1 filter
A Spectral Approach to Analyzing Belief Propagation for 3-Coloring
Amin Coja-Oghlan, Elchanan Mossel, Dan Vilenchik
Contributing to the rigorous understanding of BP, in this paper we relate the convergence of BP to spectral properties of the graph. This encompasses a result for random graphs wit…
Reconstruction of Markov Random Fields from Samples: Some Easy Observations and Algorithms
Guy Bresler, Elchanan Mossel, Allan Sly
Markov random fields are used to model high dimensional distributions in a number of applied areas. Much recent interest has been devoted to the reconstruction of the dependency st…
Incomplete Lineage Sorting: Consistent Phylogeny Estimation From Multiple Loci
Elchanan Mossel, Sebastien Roch
We introduce a simple algorithm for reconstructing phylogenies from multiple gene trees in the presence of incomplete lineage sorting, that is, when the topology of the gene trees…
Sorting and Selection in Posets
Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel +2
Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study a more general setting, in which some pairs…
Noisy Sorting Without Resampling
Mark Braverman, Elchanan Mossel
In this paper we study noisy sorting without re-sampling. In this problem there is an unknown order where is a permutation on elements. The inpu…
Gibbs Rapidly Samples Colorings of G(n,d/n)
Elchanan Mossel, Allan Sly
Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sam…
Mixed-up trees: the structure of phylogenetic mixtures
Frederick A. Matsen, Elchanan Mossel, Mike Steel
In this paper we apply new geometric and combinatorial methods to the study of phylogenetic mixtures. The focus of the geometric approach is to describe the geometry of phylogeneti…
Rapid Mixing of Gibbs Sampling on Graphs that are Sparse on Average
Elchanan Mossel, Allan Sly
In this work we show that for every and the Ising model defined on , there exists a , such that for all with probability going to 1 as $n \…
Connectivity and equilibrium in random games
Constantinos Daskalakis, Alexandros G. Dimakis, Elchanan Mossel
We study how the structure of the interaction graph of a game affects the existence of pure Nash equilibria. In particular, for a fixed interaction graph, we are interested in whet…
Gaussian Bounds for Noise Correlation of Functions
Elchanan Mossel
In this paper we derive tight bounds on the expected value of products of {\em low influence} functions defined on correlated probability spaces. The proofs are based on extending…
On the hardness of sampling independent sets beyond the tree threshold
Elchanan Mossel, Dror Weitz, Nicholas Wormald
We consider local Markov chain Monte-Carlo algorithms for sampling from the weighted distribution of independent sets with activity , where the weight of an independent set …