658 citations · 2.2k across the 187 of their papers we have counts for
9 papers · 1 filter
Complete convergence of message passing algorithms for some satisfiability problems
Uriel Feige, Elchanan Mossel, Dan Vilenchik
In this paper we analyze the performance of Warning Propagation, a popular message passing algorithm. We show that for 3CNF formulas drawn from a certain distribution over random s…
Scaling Limits for Width Two Partially Ordered Sets: The Incomparability Window
Nayantara Bhatnagar, Nick Crawford, Elchanan Mossel +1
We study the structure of a uniformly randomly chosen partial order of width 2 on n elements. We show that under the appropriate scaling, the number of incomparable elements conver…
Phylogenetic information complexity: Is testing a tree easier than finding it?
Mike Steel, Laszlo Szekely, Elchanan Mossel
Phylogenetic trees describe the evolutionary history of a group of present-day species from a common ancestor. These trees are typically reconstructed from aligned DNA sequence dat…
Agnostically Learning Juntas from Random Walks
Jan Arpe, Elchanan Mossel
We prove that the class of functions g:{-1,+1}^n -> {-1,+1} that only depend on an unknown subset of k<<n variables (so-called k-juntas) is agnostically learnable from a random wal…
Multiple Random Oracles Are Better Than One
Jan Arpe, Elchanan Mossel
We study the problem of learning k-juntas given access to examples drawn from a number of different product distributions. Thus we wish to learn a function f : {-1,1}^n -> {-1,1} t…
Branching Process approach for 2-SAT thresholds
Elchanan Mossel, Arnab Sen
It is well known that, as tends to infinity, the probability of satisfiability for a random 2-SAT formula on variables, where each clause occurs independently with probabil…
Approximation Resistant Predicates From Pairwise Independence
Per Austrin, Elchanan Mossel
We study the approximability of predicates on variables from a domain , and give a new sufficient condition for such predicates to be approximation resistant under the Uni…
Shrinkage Effect in Ancestral Maximum Likelihood
Elchanan Mossel, Sebastien Roch, Mike Steel
Ancestral maximum likelihood (AML) is a method that simultaneously reconstructs a phylogenetic tree and ancestral sequences from extant data (sequences at the leaves). The tree and…
Phylogenies without Branch Bounds: Contracting the Short, Pruning the Deep
Constantinos Daskalakis, Elchanan Mossel, Sebastien Roch
We introduce a new phylogenetic reconstruction algorithm which, unlike most previous rigorous inference techniques, does not rely on assumptions regarding the branch lengths or the…