Keller, Nathan, Mossel, Elchanan, Sen, Arnab
We present a new definition of influences in product spaces of continuous distributions. Our definition is geometric, and for monotone sets it is identical with the measure of the boundary with...
The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem (2009)
Isaksson, Marcus, Kindler, Guy, Mossel, Elchanan
We prove a quantitative version of the Gibbard-Satterthwaite theorem. We show that a uniformly chosen voter profile for a neutral social choice function $f$ of $q \geq 4$ alternatives and $n$ voters...
Complete Characterization of Functions Satisfying the Conditions of Arrow's Theorem (2009)
Arrow's theorem implies that a social choice function satisfying Transitivity, the Pareto Principle (Unanimity) and Independence of Irrelevant Alternatives (IIA) must be dictatorial. When non-strict...
Sorting from Noisy Information (2009)
Braverman, Mark, Mossel, Elchanan
This paper studies problems of inferring order given noisy information. In these problems there is an unknown order (permutation) $\pi$ on $n$ elements denoted by $1,...,n$. We assume that...
The Complexity of Distinguishing Markov Random Fields (2009)
Andrej Bogdanov, Elchanan Mossel, Salil Vadhan
Abstract. Markov random fields are often used to model high dimensional distributions in a number of applied areas. A number of recent papers have studied the problem of reconstructing a dependency...
Mossel, Elchanan, Papadimitriou, Christos, Schapira, Michael, Singer, Yaron
The existence of incentive-compatible computationally-efficient protocols for combinatorial auctions with decent approximation ratios is the paradigmatic problem in computational mechanism design. It...
Iterative Maximum Likelihood on Networks (2009)
We consider n agents located on the vertices of a connected graph. Each agent v receives a signal X_v(0)~N(s, 1) where s is an unknown quantity. A natural iterative way of estimating s is to perform...
Noise Correlation Bounds for Uniform Low Degree Functions (2009)
Austrin, Per, Mossel, Elchanan
We study correlation bounds under pairwise independent distributions for functions with no large Fourier coefficients. Functions in which all Fourier coefficients are bounded by $\delta$ are called...
Maximally Stable Gaussian Partitions with Discrete Applications (2009)
Isaksson, Marcus, Mossel, Elchanan
Gaussian noise stability results have recently played an important role in proving results in hardness of approximation in computer science and in the study of voting schemes in social choice. We...
Exact Thresholds for Ising-Gibbs Samplers on General Graphs (2009)
We establish tight results for rapid mixing of Gibbs Samplers for the Ferromagnetic Ising model on general graphs. We show that if $(d-1) \tanh \beta < 1$, then there exists a constant $C$ such that...
A Quantitative Arrow Theorem (2009)
Arrow's Impossibility Theorem states that any constitution which satisfies Independence of Irrelevant Alternatives (IIA) and Unanimity and is not a Dictator has to be non-transitive. In this paper we...
Elchanan Mossel, Oded Regev, Jeffrey E. Steif, Benny Sudakov
In this paper we study non-interactive correlation distillation (NICD), a generalization of noise sensitivity previously considered in [5, 31, 39]. We extend the model to NICD on trees. In this model...
Abstract A New Look at Survey Propagation and its Generalizations (2009)
Elitza Maneva, Elchanan Mossel, Martin J. Wainwright
We study the survey propagation algorithm [19, 5, 4], which is an iterative technique that appears to be very effective in solving random k-SAT problems even with densities close to threshold. We...
Nader Bshouty, Elchanan Mossel, Rocco A. Servedio
We consider a model of learning Boolean functions from examples generated by a uniform random walk on {0, 1} n. We give a polynomial time algorithm for learning decision trees and DNF formulas in...
Arrow's Impossibility Theorem Without Unanimity (2009)
Arrow's Impossibility Theorem states that any constitution which satisfies Transitivity, Independence of Irrelevant Alternatives and Unanimity is a dictatorship. In this paper we derive a proof that...
Nader Bshouty, Elchanan Mossel, Rocco A. Servedio
We consider a model of learning Boolean functions from examples generated by a uniform random walk on {0, 1} n. We give a polynomial time algorithm for learning decision trees and DNF formulas in...
Complete convergence of message passing algorithms for some satisfiability problems (2008)
Feige, Uriel, Mossel, Elchanan, Vilenchik, Dan
Experimental results show that certain message passing algorithms, namely, Survey Propagation, are very effective in finding satisfying assignments for random satisfiable 3CNF formulas which are...
Scaling Limits for Width Two Partially Ordered Sets: The Incomparability Window (2008)
Bhatnagar, Nayantara, Crawford, Nick, Mossel, Elchanan, Sen, Arnab
We study the structure of a uniformly randomly chosen partial order of width 2 on n elements. We analyze the local structure by studying the number of elements incomparable to a random element in the...
Phylogenetic information complexity: Is testing a tree easier than finding it? (2008)
Steel, Mike, Szekely, Laszlo, Mossel, Elchanan
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 data. In this paper we...
Agnostically Learning Juntas from Random Walks (2008)
We prove that the class of functions g:{-1,+1}^n -> {-1,+1} that only depend on an unknown subset of k {-1,+1}, finds with probability at least 1-delta a k-junta that is (opt(f)+epsilon)-close to f,...
Multiple Random Oracles Are Better Than One (2008)
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} that depends on k...
Name Dr, Jan Arpe, Supervisor Prof, Elchanan Mossel, Prof Dr. Georg
University, Sapporo)
ABSTRACT Learning Nonsingular Phylogenies and Hidden Markov Models (2008)
In this paper, we study the problem of learning phylogenies and hidden Markov models. We call a Markov model nonsingular if all transition matrices have determinants bounded away from 0 (and 1). We...
Elchanan Mossel, Oded Regev, Jeffrey E. Steif, Benny Sudakov
In this paper we study the problem of non-interactive correlation distillation (NICD), a generalization of noise sensitivity previously considered in [5, 31, 39]. We extend the model to NICD on...
On the Complexity of Approximating the V C Dimension (2008)
Elchanan Mossel, Christopher Umans
We study the complexity of approximating the V C dimension of a collection of sets, when the sets are encoded succinctly by a small circuit. We show that this problem is: âą ÎŁ p 3-hard to...
Abstract Online Conflict-Free Coloring for Intervals (2008)
Amos Fiat, Meital Levy, Elchanan Mossel, JĂĄnos Pach, Micha Sharir, Shakhar Smorodinsky, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Branching Process approach for 2-SAT thresholds (2008)
It is well known that, as $n$ tends to infinity, the probability of satisfiability for a random 2-SAT formula on $n$ variables, where each clause occurs independently with probability $\alpha/2n$,...
Approximation Resistant Predicates From Pairwise Independence (2008)
Austrin, Per, Mossel, Elchanan
We study the approximability of predicates on $k$ variables from a domain $[q]$, and give a new sufficient condition for such predicates to be approximation resistant under the Unique Games...
Shrinkage Effect in Ancestral Maximum Likelihood (2008)
Mossel, Elchanan, Roch, Sebastien, Steel, Mike
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 ancestral...
Elchanan Mossel, Jeffrey E. Steif
* * Most of this work was done while the author was a student at Massachusetts Institute of Technology. This material is based upon work supported by the National Science Foundation under agreement...
Phylogenies without Branch Bounds: Contracting the Short, Pruning the Deep (2008)
Daskalakis, Constantinos, Mossel, Elchanan, Roch, Sebastien
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 depth of the tree....
Shrinkage Effect in Ancestral Maximum Likelihood (2008)
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 ancestral...
Evolutionary Trees and the Ising Model on the Bethe Lattice: a Proof of Steelâs Conjecture (2008)
Constantinos Daskalakis, Elchanan Mossel, SĂ©bastien Roch
One of the major tasks of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on the true evolutionary tree. Given...
Approximation Resistant Predicates From Pairwise Independence (2008)
We study the approximability of predicates on k variables from a domain [q], and give a new sufficient condition for such predicates to be approximation resistant under the Unique Games Conjecture....
PHYLOGENETIC INFORMATION COMPLEXITY: IS TESTING A TREE EASIER THAN FINDING IT? (2008)
Mike Steel, Laszlo Székely, Elchanan Mossel, Mike Steel, Mike Steel, Laszlo Székely, ...
Abstract. 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 data. In...
A Spectral Approach to Analyzing Belief Propagation for 3-Coloring (2007)
Coja-Oghlan, Amin, Mossel, Elchanan, Vilenchik, Dan
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 with a ``planted''...
Svante Janson, Elchanan Mossel
reconstruction on trees is determined by the second eigenvalue
Claire Kenyon, Elchanan Mossel, Yuval Peres
We study discrete time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show...
Path properties of Brownian Motion (2007)
and wrote the rst draft of the notes: Diego Garcia, Yoram Gat, Diogo A. Gomes, Charles
On random graph homomorphisms into Z (2007)
Itai Benjamini, Elchanan Mossel
Given a bipartite connected nite graph G = (V; E) and a vertex v0 2 V, we consider uniform probability measure on the set of graph homomorphisms f: V! Z satisfying f(v0) = 0. This measure can be...
An Invitation to Sample Paths of Brownian Motion (2007)
and wrote the rst draft of the notes: Diego Garcia, Yoram Gat, Diogo A. Gomes, Charles
Abstract Draw planes in IR (2007)
Johan Jonasson, Elchanan Mossel, Yuval Peres
that are orthogonal to the x axis, and intersect the x axis at the points of a Poisson process with intensity ; similarly, draw planes orthogonal to the y and z axes using independent Poisson...
Abstract Draw planes in IR (2007)
Johan Jonasson, Elchanan Mossel, Yuval Peres
that are orthogonal to the x axis, and intersect the x axis at the points of a Poisson process with intensity; similarly, draw planes orthogonal to the y and z axes using independent Poisson...
An Invitation to Sample (2007)
Paths Of Brownian, Yuval Peres, Elchanan Mossel, Yimin Xiao, Frédéric LatrémoliÚre, Wei Li, ...
Contents Chapter 1. Brownian Motion 1 1. Motivation -- Intersection of Brownian paths 1 2. Gaussian random variables 1 3. Levy's construction of Brownian motion 4 4. Basic properties of Brownian...
On #-Biased Generators in NC 0 (2007)
Elchanan Mossel, Amir Shpilka, Luca Trevisan
Cryan and Miltersen [CM01] recently considered the question of whether there can be a pseudorandom generator in NC 0, that is, a pseudorandom generator that maps n bits strings to m bits strings and...
On random graph homomorphisms into Z (2007)
Itai Benjamini, Olle Haggstrom, Elchanan Mossel
Given a bipartite connected finite graph G = (V; E) and a vertex v0 2 V, we consider uniform probability measure on the set of graph homomorphisms f: V! Z satisfying f(v0) = 0. This measure can be...
Elchanan Mossel, Ryan O'Donnell, Oded Regev, Jeffrey E. Steif, Benny Sudakov
In this paper we study the problem of non-interactive correlation distillation (NICD), a generalization of noise sensitivity previously considered in [5, 31, 39]. We extend the model to NICD on...
Incomplete Lineage Sorting: Consistent Phylogeny Estimation From Multiple Loci (2007)
Mossel, Elchanan, Roch, Sebastien
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 may differ from...
Gibbs Rapidly Samples Colorings of G(n,d/n) (2007)
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 sampling on the...
Sorting and Selection in Posets (2007)
Daskalakis, Constantinos, Karp, Richard M., Mossel, Elchanan, Riesenfeld, Samantha, Verbin, Elad
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 of objects are...
Noisy Sorting Without Resampling (2007)
Braverman, Mark, Mossel, Elchanan
In this paper we study noisy sorting without re-sampling. In this problem there is an unknown order $a_{\pi(1)} < ... < a_{\pi(n)}$ where $\pi$ is a permutation on $n$ elements. The input is the...
Mixed-up trees: the structure of phylogenetic mixtures (2007)
Matsen, Frederick A., Mossel, Elchanan, Steel, Mike
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 phylogenetic mixture...
Rapid Mixing of Gibbs Sampling on Graphs that are Sparse on Average (2007)
In this work we show that for every $d < \infty$ and the Ising model defined on $G(n,d/n)$, there exists a $\beta_d > 0$, such that for all $\beta < \beta_d$ with probability going to 1 as $n \to...
Connectivity and Equilibrium in Random Games (2007)
Daskalakis, Constantinos, Dimakis, Alexandros G., Mossel, Elchanan
We study how the structure of the interaction graph affects the Nash equilibria of the resulting game. In particular, for a fixed interaction graph, we are interested if there exist Nash equilibria...
Gaussian Bounds for Noise Correlation of Functions (2007)
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 Fourier theory to...
On the hardness of sampling independent sets beyond the tree threshold (2007)
Mossel, Elchanan, Weitz, Dror, Wormald, Nicholas
We consider local Markov chain Monte-Carlo algorithms for sampling from the weighted distribution of independent sets with activity $\l$, where the weight of an independent set $I$ is $\l^{|I|}$. A...
Sorting and Selection in Posets (2007)
Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld, Elad Verbin
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 of objects are...
On the submodularity of influence in social networks (2007)
Elchanan Mossel, Sebastien Roch
We prove and extend a conjecture of Kempe, Kleinberg, and Tardos (KKT) on the spread of influence in social networks. A social network can be represented by a directed graph where the nodes are...
On the Submodularity of Influence in Social Networks (2006)
Mossel, Elchanan, Roch, Sebastien
We prove and extend a conjecture of Kempe, Kleinberg, and Tardos (KKT) on the spread of influence in social networks. A social network can be represented by a directed graph where the nodes are...
Limitations of Markov chain Monte Carlo algorithms for Bayesian inference of phylogeny (2006)
Mossel, Elchanan, Vigoda, Eric
Markov chain Monte Carlo algorithms play a key role in the Bayesian approach to phylogenetic inference. In this paper, we present the first theoretical work analyzing the rate of convergence of...
Mafia: A theoretical study of players and coalitions in a partial information environment (2006)
Braverman, Mark, Etesami, Omid, Mossel, Elchanan
In this paper, we study a game called ``Mafia,'' in which different players have different types of information, communication and functionality. The players communicate and function in a way that...
Learning nonsingular phylogenies and hidden Markov models (2006)
Mossel, Elchanan, Roch, SĂ©bastien
In this paper we study the problem of learning phylogenies and hidden Markov models. We call a Markov model nonsingular if all transition matrices have determinants bounded away from 0 (and 1). We...
The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels (2006)
Borgs, Christian, Chayes, Jennifer, Mossel, Elchanan, Roch, Sebastien
We establish the exact threshold for the reconstruction problem for a binary asymmetric channel on the b-ary tree, provided that the asymmetry is sufficiently small. This is the first exact...
Online conflict-free coloring for intervals. (2006)
Fiat, Amos, MatouĆĄek, JiĆĂ, Mossel, Elchanan, Pach, JĂĄnos, Sharir, Micha, Smorodinsky, Shakhar, ...
Optimal phylogenetic reconstruction (2006)
Constantinos Daskalakis, Elchanan Mossel, SĂ©bastien Roch
One of the major tasks of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. This problem is of critical importance in almost all areas of biology and has a very...
Conditional hardness for approximate coloring (2006)
Irit Dinur, Elchanan Mossel, Oded Regev
We study the APPROXIMATE-COLORING(q, Q) problem: Given a graph G, decide whether Ï(G) †q or Ï(G) â„ Q (where Ï(G) is the chromatic number of G). We derive conditional hardness for this problem...
Online conflict-free coloring for intervals (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel
Abstract. We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the...
Online Conflict-Free Coloring for Intervals 1 (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, JĂĄnos Pach, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Online Conflict-Free Coloring for Intervals 1 (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, JĂĄnos Pach, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Uriel Feige, Elchanan Mossel, Dan Vilenchik
convergence of message passing algorithms for some
Online conflict-free coloring for intervals (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Ji RĂ, Matou Sek, ...
Abstract. We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the...
Complete convergence of message passing algorithms for some satisfiability problems (2006)
Uriel Feige, Elchanan Mossel, Dan Vilenchik
Abstract. Experimental results show that certain message passing algorithms, namely, survey propagation, are very effective in finding satisfying assignments in random satisfiable 3CNF formulas. In...
Conditional hardness for approximate coloring (2006)
Irit Dinur, Elchanan Mossel, Oded Regev
We study the APPROXIMATE-COLORING(q, Q) problem: Given a graph G, decide whether Ï(G) †q or Ï(G) â„ Q. We derive conditional hardness for this problem for any constant 3 †q < Q. For q â„...
Nader Bshouty, Elchanan Mossel, Rocco A. Servedio
We consider a model of learning Boolean functions from examples generated by a uniform random walk on {0, 1} n. We give a polynomial time algorithm for learning decision trees and DNF formulas in...
Evolutionary Trees and the Ising Model on the Bethe Lattice: a Proof of Steel's Conjecture (2005)
Daskalakis, Constantinos, Mossel, Elchanan, Roch, Sebastien
One of the major tasks of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on the true evolutionary tree. Given...
Slow Emergence of Cooperation for Win-Stay Lose-Shift on Trees (2005)
Mossel, Elchanan, Roch, Sebastien
We consider a group of agents on a graph who repeatedly play the prisoner's dilemma game against their neighbors. The players adapt their actions to the past behavior of their opponents by applying...
Limitations of Markov chain Monte Carlo algorithms for Bayesian Inference of phylogeny (2005)
Mossel, Elchanan, Vigoda, Eric
Markov chain Monte Carlo algorithms play a key role in the Bayesian approach to phylogenetic inference. In this paper, we present the first theoretical work analyzing the rate of convergence of...
Conditional Hardness for Approximate Coloring (2005)
Dinur, Irit, Mossel, Elchanan, Regev, Oded
We study the coloring problem: Given a graph G, decide whether $c(G) \leq q$ or $c(G) \ge Q$, where c(G) is the chromatic number of G. We derive conditional hardness for this problem for any constant...
Noise stability of functions with low influences: invariance and optimality (2005)
Mossel, Elchanan, O'Donnell, Ryan, Oleszkiewicz, Krzysztof
In this paper we study functions with low influences on product probability spaces. The analysis of boolean functions with low influences has become a central problem in discrete Fourier analysis. It...
Mixing times of the biased card shuffling and the asymmetric exclusion process (2005)
Benjamini, Itai, Berger, Noam, Hoffman, Christopher, Mossel, Elchanan
Consider the following method of card shuffling. Start with a deck of N cards numbered 1 through N. Fix a parameter p between 0 and 1. In this model a "shuffle" consists of uniformly selecting a pair...
Learning nonsingular phylogenies and hidden Markov models (2005)
Mossel, Elchanan, Roch, SĂ©bastien
In this paper we study the problem of learning phylogenies and hidden Markov models. We call a Markov model nonsingular if all transition matrices have determinants bounded away from 0 (and 1). We...
Learning Nonsingular Phylogenies and Hidden Markov Models (2005)
Elchanan Mossel, SĂ©bastien Roch
In this paper, we study the problem of learning phylogenies and hidden Markov models. We call the Markov model nonsingular if all transtion matrices have determinants bounded away from 0 (and 1). We...
A new look at survey propagation and its generalizations (2005)
Elitza Maneva, Elchanan Mossel, Martin J. Wainwright
We study the survey propagation algorithm [18, 4, 3], which is an iterative technique that appears to be very effective in solving random k-SAT problems even with densities close to threshold. We...
A new look at survey propagation and its generalizations (2005)
Elitza Maneva, Elchanan Mossel, J. Wainwright
Abstract. This article provides a new conceptual perspective on survey propagation, which is an iterative algorithm recently introduced by the statistical physics community that is very effective in...
Subhash Khot, Guy Kindler, Elchanan Mossel
In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of α GW + É, for all É> 0; here α GW â.878567 denotes the...
Subhash Khot, Guy Kindler, Elchanan Mossel
In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of αGW + É, for all É> 0; here αGW â.878567 denotes the...
Elchanan Mossel, Krzysztof Oleszkiewicz
stability of functions with low influences:
Mossel, Elchanan, O'Donnell, Ryan, Regev, Oded, Steif, Jeffrey, Sudakov, Benjamin
In this paper we study non-interactive correlation distillation (NICD), a generalization of the study of noise sensitivity of boolean functions. We extend the model to NICD on trees. In this model...
A New Look at Survey Propagation and its Generalizations (2004)
Maneva, Eliza N., Mossel, Elchanan, Wainwright, Martin J.
This paper provides a new conceptual perspective on survey propagation, which is an iterative algorithm recently introduced by the statistical physics community that is very effective in solving...
Robust reconstruction on trees is determined by the second eigenvalue (2004)
Janson, Svante, Mossel, Elchanan
Consider a Markov chain on an infinite tree T=(V,E) rooted at Ï. In such a chain, once the initial root state Ï({Ï}) is chosen, each vertex iteratively chooses its state from the one of its parent...
Coin flipping from a cosmic source: On error correction of truly random bits (2004)
Mossel, Elchanan, O'Donnell, Ryan
We study a problem related to coin flipping, coding theory, and noise sensitivity. Consider a source of truly random bits $x \in \bits^n$, and $k$ parties, who have noisy versions of the source bits...
A Law of Large Numbers for Weighted Majority (2004)
Haggstrom, Olle, Kalai, Gil, Mossel, Elchanan
Consider an election between two candidates in which the voters' choices are random and independent and the probability of a voter choosing the first candidate is $p>1/2$. Condorcet's Jury Theorem...
Random autocatalytic networks (2004)
We determine conditions under which a random biochemical system is likely to contain a subsystem that is both autocatalytic and able to survive on some ambient `food' source. Such systems have...
How much can evolved characters tell us about the tree that generated them? (2004)
In this paper we review some recent results that shed light on a fundamental question in molecular systematics: how much phylogenetic `signal' can we expect from characters that have evolved under...
Survey: Information flow on trees (2004)
Consider a tree network T, where each edge acts as an independent copy of a given channel M, and information is propagated from the root. For which T and M does the configuration obtained at level n...
Robust reconstruction on trees is determined by the second eigenvalue (2004)
Janson, Svante, Mossel, Elchanan
Consider a Markov chain on an infinite tree T=(V,E) rooted at \rho. In such a chain, once the initial root state \sigma(\rho) is chosen, each vertex iteratively chooses its state from the one of its...
Shuffling by semi-random transpositions (2004)
Mossel, Elchanan, Peres, Yuval, Sinclair, Alistair
In the cyclic-to-random shuffle, we are given n cards arranged in a circle. At step k, we exchange the k'th card along the circle with a uniformly chosen random card. The problem of determining the...
Distorted metrics on trees and phylogenetic forests (2004)
We study distorted metrics on binary trees in the context of phylogenetic reconstruction. Given a binary tree $T$ on $n$ leaves with a path metric $d$, consider the pairwise distances $\{d(u,v)\}$...
Online Conflict-Free Coloring for Intervals 1 (2004)
Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, JĂĄnos Pach, Micha Sharir, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs (2004)
Subhash Khot, Guy Kindler, Elchanan Mossel
In this paper we give evidence suggesting that MAX-CUT is NP-hard to approximate to within a factor of αGW+É, for all É> 0, where αGW denotes the approximation ratio achieved by the...
The survey-propagati... (2004)
Elitza Maneva, Elchanan Mossel, Martin J. Wainwright
We study the survey propagation algorithm [18, 4, 3], which is an iterative technique that appears to be very effective in solving random k-SAT problems even with densities close to threshold. We...
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs (2004)
Subhash Khot, Elchanan Mossel, Guy Kindler
In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of αGW + É, for all É> 0; here αGW â.878567 denotes the...
A Phase Transition for a Random Cluster Model on Phylogenetic Trees (2004)
We investigate a simple model that generates random partitions of the leaf set of a tree. Of particular interest is the reconstruction question: what number k of independent samples (partitions) are...
A Law of Large Numbers for Weighted Majority Olle H"aggstr"om * Chalmers University (2004)
Abstract Consider an election between two candidates in which the voters ' choices are random andindependent and the probability of a voter choosing the first candidate is p> 1/2....
Online Conflict-Free Coloring for Intervals 1 (2004)
Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, JĂĄnos Pach, Micha Sharir, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
On approximately fair allocations of indivisible goods (2004)
Richard Lipton, Evangelos Markakis, Elchanan Mossel, Amin Saberi
Preliminary version Abstract (2004)
Subhash Khot, Elchanan Mossel, Guy Kindler
In this paper we give evidence that it is NP-hard to approximate MAX-CUT to within a factor of α GW+É, for all É> 0. Here α GW denotes the approximation ratio achieved by the...
Glauber Dynamics on Trees and Hyperbolic Graphs (2003)
Berger, Noam, Kenyon, Claire, Mossel, Elchanan, Peres, Yuval
We study continuous time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with $n$ vertices and of bounded degree. We...
Information flow on trees (2003)
Mossel, Elchanan, Peres, Yuval
Consider a tree network $T$, where each edge acts as an independent copy of a given channel $M$, and information is propagated from the root. For which $T$ and $M$ does the configuration obtained at...
Phase transitions in Phylogeny (2003)
We apply the theory of markov random fields on trees to derive a phase transition in the number of samples needed in order to reconstruct phylogenies. We consider the Cavender-Farris-Neyman model of...
New coins from old: computing with unknown bias (2003)
Mossel, Elchanan, Peres, Yuval
Suppose that we are given a function f : (0,1) -> (0,1) and, for some unknown p in (0,1), a sequence of independent tosses of a p-coin (i.e., a coin with probability p of ``heads''). For which...
On epsilon-biased generators in NC0 (2003)
Elchanan Mossel, Amir Shpilka, Luca Trevisan
Cryan and Miltersen [8] recently considered the question of whether there can be a pseudorandom generator in NC0, that is, a pseudorandom generator that maps n-bit strings to m-bit strings such that...
Phase transitions in phylogeny (2003)
Abstract. We apply the theory of Markov random fields on trees to derive a phase transition in the number of samples needed in order to reconstruct phylogenies. We consider the Cavender-Farris-Neyman...
Elchanan Mossel, Rocco A. Servedio
We consider a fundamental problem in computational learning theory: learning an arbitrary Boolean function which depends on an unknown set of k out of n Boolean variables. We give an algorithm for...
On epsilon-biased generators in NC0 (2003)
Elchanan Mossel, Amir Shpilka, Luca Trevisan
Cryan and Miltersen [8] recently considered the question of whether there can be a pseudorandom generator in NC0, that is, a pseudorandom generator that maps n-bit strings to m-bit strings such that...
Elchanan Mossel, Rocco A. Servedio
We consider a fundamental problem in computational learning theory: learning an arbitrary Boolean function which depends on an unknown set of k out of n Boolean variables. We give an algorithm for...
It is known that for all monotone functions f: {0, 1} n â {0, 1}, if x â {0, 1} n is chosen uniformly at random and y is obtained from x by flipping each of the bits of x independently with...
Learning DNF from Random Walks (2003)
Nader Bshouty, Elchanan Mossel, Rocco A. Servedio
We consider a model of learning Boolean functions from examples generated by a uniform random walk on {0,
On the Noise Sensitivity of Monotone Functions (2003)
Elchanan Mossel, Ryan O'Donnell
It is known that for all monotone functions f : {0, 1}, if x is chosen uniformly at random and y is obtained from x by flipping each of the bits of x independently with probability # = n -# , then...
Robust reconstruction on trees is determined by the second eigenvalue (2003)
Consider a Markov chain on an infinite tree T = (V, E) rooted at Ï. In such a chain, once the initial root state Ï(Ï) is chosen, each vertex iteratively chooses its state from the one of its...
Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio
We consider a fundamental problem in computational learning theory: learning an arbitrary Boolean function which depends on an unknown set of k out of n Boolean variables. We give an algorithm for...
On the impossibility of reconstructing ancestral data and phylogenies (2003)
We prove that it is impossible to reconstruct ancestral data at the root of âdeep â phylogenetic trees with high mutation rates. Moreover, we prove that it is impossible to reconstruct the...
Mixing times of the biased card shuffling and the asymmetric exclusion process (2002)
Benjamini, Itai, Berger, Noam, Hoffman, Christopher, Mossel, Elchanan
Consider the following method of card shuffling. Start with a deck of $N$ cards numbered 1 through N. Fix a parameter $p$ between 0 and 1. In this model a ``shuffle'' consists of uniformly selecting...
The Minesweeper game: Percolation and Complexity (2002)
We study a model motivated by the minesweeper game. In this model one starts with percolation of mines on the sites of the lattice Z d, and then tries to find an infinite path of mine free sites. At...
Coin flipping from a cosmic source: On error correction of truly random bits (2002)
Elchanan Mossel, Ryan O'Donnell
We study a new problem related to coin flipping, coding theory, and noise sensitivity. Consider a source of truly random bits x ∈ {0, 1}^n, and k parties, who have noisy versions of the...
Svante Janson, Elchanan Mossel
reconstruction on trees is determined by the second eigenvalue
Mixing Times of the biased card shuffling and the asymmetric exclusion process (2002)
Itai Benjamini, Noam Berger, Christopher Hoffman, Elchanan Mossel
Consider the following method of card shu#ing. Start with a deck of N cards numbered 1 through N . Fix a parameter p between 0 and 1. In this model a "shu#e" consists of uniformly selecting...
Suppose that we are given a function f: (0, 1) â (0, 1) and, for some unknown p â (0, 1), a sequence of independent tosses of a p-coin (i.e., a coin with probability p of âheadsâ). For which...
On the noise sensitivity of monotone functions (2002)
It is known that for all monotone functions f: {0, 1} n â {0, 1}, if x â {0, 1} n is chosen uniformly at random and y is obtained from x by flipping each of the bits of x independently with...
Information flow on trees (2001)
Mossel, Elchanan, Peres, Yuval
Consider a tree network $T$, where each edge acts as an independent copy of a given channel $M$, and information is propagated from the root. For which $T$ and $M$ does the configuration obtained at...
Reconstruction on Trees: Beating the Second Eigenvalue (2001)
We consider a process in which information is transmitted from a given root node on a noisy -dary tree network T. We start with a uniform symbol taken from an alphabet \(\mathcal{A}\). Each edge of...
On the complexity of approximating the vc dimension (2001)
We study the complexity of approximating the VC dimension of a collection of sets, when the sets are encoded succinctly by a small circuit. We show that this problem is âą ÎŁ p 3-hard to approximate...
Reconstruction on trees: Beating the second eigenvalue (2001)
We consider a process in which information is transmitted from a given root node on a noisy d-ary tree network T. We start with a uniform symbol taken from an alphabet A. Each edge of the tree is an...
Reconstruction on trees: Beating the second eigenvalue (2001)
We consider a process in which information is transmitted from a given root node on a noisy d-ary tree network T. We start with a uniform symbol taken from an alphabet A. Each edge of the tree is an...
On the mixing time of simple random walk on the super critical percolation cluster (2000)
Benjamini, Itai, Mossel, Elchanan
We study the robustness under perturbations of mixing times, by studying mixing times of random walks in percolation clusters inside boxes in $\Z^d$. We show that for $d \geq 2$ and $p > p_c(\Z^d)$,...
HÀggström, Olle, Mossel, Elchanan
A few years ago, Grimmett, Kesten and Zhang proved that for supercritical bond percolation on $\mathbf{Z}^3$, simple random walk on the infinite cluster is a.s. transient. We generalize this result...
Energy of flows on percolation clusters (1998)
Christopher Hoffman, Elchanan Mossel
It is well known for which gauge functions H there exists a flow on Z d with finite H energy. In this paper we discuss the robustness under random thinning of edges of the existence of such flows....
Nearest-neighbor walks with low predictability profile and percolation (1998)
Olle HÀggström, Elchanan Mossel
A few years ago, Grimmett, Kesten and Zhang proved that for supercritical bond percolation on Z 3, simple random walk on the infinite cluster is a.s. transient. We generalize this result to a class...
Energy of flows on percolation clusters (1998)
Christopher Hoffman, Elchanan Mossel
It is well known for which gauge functions H there exists a flow on Z d with finite H energy. In this paper we discuss the robustness under random thinning of edges of the existence of such flows....
Nearest-neighbor walks with low predictability profile and percolation (1998)
Olle Haggstrom, Elchanan Mossel
A few years ago, Grimmett, Kesten and Zhang proved that for supercritical bond percolation on Z 3, simple random walk on the infinite cluster is a.s. transient. We generalize this result to a class...
Energy of flows on percolation clusters (1998)
Christopher Hoffman, Elchanan Mossel
It is well known for which gauge functions H there exists a flow on Z d with finite H energy. In this paper we discuss the robustness under random thinning of edges of the existence of such flows....
Recursive reconstruction on periodic trees (1998)
A periodic tree Tn consists of full n-level copies of a nite tree T. The tree Tn is labeled by random bits. The root label is chosen randomly, and the probability of two adjacent vertices to have the...
On random graph homomorphisms into Z (1998)
Itai Benjamini, Olle HÀggström, Elchanan Mossel
Given a bipartite connected finite graph G = (V; E) and a vertex v 0 2 V , we consider uniform probability measure on the set of graph homomorphisms f : V ! Z satisfying f(v 0 ) = 0. This measure can...
Energy of Flows on Percolation Clusters Christopher Homan (1998)
Christopher Hoffman, Elchanan Mossel
It is well known for which gauge functions H there exists a flow on Z with finite H energy. In this paper we discuss the robustness under random thinning of edges of the existence of such flows....
Recursive reconstruction on periodic trees (1998)
A periodic tree Tn consists of full n-level copies of a finite tree T. The tree Tn is labeled by random bits. The root label is chosen randomly, and the probability of two adjacent vertices to have...
Elchanan Mossel, Amir Shpilka, Luca Trevisan
Cryan and Miltersen [7] recently considered the question of whether there can be a pseudorandom generator in NC0, that is, a pseudorandom generator that maps n bits strings to m bits strings and such...
In the cyclic-to-random shuffle, we are given n cards arranged in a circle. At step k, we exchange the kâth card along the circle with a uniformly chosen random card. The problem of determining the...
A Law of Large Numbers for Weighted Majority
Olle Haggstrom, Gil Kalai, Elchanan Mossel
Consider an election between two candidates in which the votersâ choices are random and independent and the probability of a voter choosing the first candidate is p > 1/2. Condorcetâs Jury...