658 citations · 2.2k across the 187 of their papers we have counts for
9 papers · 1 filter
Sharp Thresholds for Monotone Non Boolean Functions and Social Choice Theory
Gil Kalai, Elchanan Mossel
A key fact in the theory of Boolean functions is that they often undergo sharp thresholds. For example: if the function is m…
Co-evolution is Incompatible with the Markov Assumption in Phylogenetics
Tamir Tuller, Elchanan Mossel
Markov models are extensively used in the analysis of molecular evolution. A recent line of research suggests that pairs of proteins with functional and physical interactions co-ev…
VC bounds on the cardinality of nearly orthogonal function classes
Lee-Ad Gottlieb, Leonid, Kontorovich +1
We bound the number of nearly orthogonal vectors with fixed VC-dimension over $\setpm^n$. Our bounds are of interest in machine learning and empirical process theory and improve pr…
On extracting common random bits from correlated sources
Andrej Bogdanov, Elchanan Mossel
Suppose Alice and Bob receive strings of unbiased independent but noisy bits from some random source. They wish to use their respective strings to extract a common sequence of rand…
Making Consensus Tractable
Elchanan Mossel, Omer Tamuz
We study a model of consensus decision making, in which a finite group of Bayesian agents has to choose between one of two courses of action. Each member of the group has a private…
The Computational Complexity of Estimating Convergence Time
Nayantara Bhatnagar, Andrej Bogdanov, Elchanan Mossel
An important problem in the implementation of Markov Chain Monte Carlo algorithms is to determine the convergence time, or the number of iterations before the chain is close to sta…
Truthful Fair Division
Elchanan Mossel, Omer Tamuz
We address the problem of fair division, or cake cutting, with the goal of finding truthful mechanisms. In the case of a general measure space ("cake") and non-atomic, additive ind…
Efficient Bayesian Learning in Social Networks with Gaussian Estimators
Elchanan Mossel, Noah Olsman, Omer Tamuz
We consider a group of Bayesian agents who try to estimate a state of the world through interaction on a social network. Each agent initially receives a private measurement…
On the inference of large phylogenies with long branches: How long is too long?
Elchanan Mossel, Sebastien Roch, Allan Sly
Recent work has highlighted deep connections between sequence-length requirements for high-probability phylogeny reconstruction and the related problem of the estimation of ancestr…