154 citations · 287 across the 28 of their papers we have counts for
5 papers · 1 filter
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…
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…
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…
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…