658 citations · 2.2k across the 187 of their papers we have counts for
12 papers · 1 filter
The weak limit of Ising models on locally tree-like graphs
Andrea Montanari, Elchanan Mossel, Allan Sly
We consider the Ising model with inverse temperature beta and without external field on sequences of graphs G_n which converge locally to the k-regular tree. We show that for such…
Geometric influences
Nathan Keller, Elchanan Mossel, Arnab Sen
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…
The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem
Marcus Isaksson, Guy Kindler, Elchanan Mossel
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 alternatives…
Sorting from Noisy Information
Mark Braverman, Elchanan Mossel
This paper studies problems of inferring order given noisy information. In these problems there is an unknown order (permutation) on elements denoted by . We assum…
Complete Characterization of Functions Satisfying the Conditions of Arrow's Theorem
Elchanan Mossel, Omer Tamuz
Arrow's theorem implies that a social choice function satisfying Transitivity, the Pareto Principle (Unanimity) and Independence of Irrelevant Alternatives (IIA) must be dictatoria…
VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension
Elchanan Mossel, Christos Papadimitriou, Michael Schapira +1
The existence of incentive-compatible computationally-efficient protocols for combinatorial auctions with decent approximation ratios is the paradigmatic problem in computational m…
Iterative Maximum Likelihood on Networks
Elchanan Mossel, Omer Tamuz
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 estimati…
Noise Correlation Bounds for Uniform Low Degree Functions
Per Austrin, Elchanan Mossel
We study correlation bounds under pairwise independent distributions for functions with no large Fourier coefficients. Functions in which all Fourier coefficients are bounded by $δ…
Maximally Stable Gaussian Partitions with Discrete Applications
Marcus Isaksson, Elchanan Mossel
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 so…
Exact thresholds for Ising-Gibbs samplers on general graphs
Elchanan Mossel, Allan Sly
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β<1,\] then there exists a constant C…
A Quantitative Arrow Theorem
Elchanan Mossel
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-transitiv…
Arrow's Impossibility Theorem Without Unanimity
Elchanan Mossel
Arrow's Impossibility Theorem states that any constitution which satisfies Transitivity, Independence of Irrelevant Alternatives (IIA) and Unanimity is a dictatorship. Wilson deriv…