154 citations · 216 across the 21 of their papers we have counts for
4 papers · 1 filter
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…
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…