Elchanan Mossel

Nayantara Bhatnagar, Nick Crawford, Elchanan Mossel, Arnab Sen: Scaling Limits for Width Two Partially Ordered Sets: The Incomparability Window. Order 30(1): 289-311 (2013)

Marcus Isaksson, Guy Kindler, Elchanan Mossel: The geometry of manipulation - A quantitative proof of the Gibbard-Satterthwaite theorem. Combinatorica 32(2): 221-250 (2012)

Lee-Ad Gottlieb, Aryeh Kontorovich, Elchanan Mossel: VC bounds on the cardinality of nearly orthogonal function classes. Discrete Mathematics 312(10): 1766-1775 (2012)

Nathan Keller, Elchanan Mossel, Tomer Schlank: A note on the Entropy/Influence conjecture. Discrete Mathematics 312(22): 3364-3372 (2012)

Elchanan Mossel, Omer Tamuz: Complete characterization of functions satisfying the conditions of Arrow's theorem. Social Choice and Welfare 39(1): 127-140 (2012)

Elchanan Mossel, Miklós Z. Rácz: A quantitative gibbard-satterthwaite theorem without neutrality. STOC 2012: 1041-1060

Elchanan Mossel, Omer Tamuz: Bundling Customers: How to Exploit Trust Among Customers to Maximize Seller Profit. CoRR abs/1202.0969 (2012)

Anindya De, Elchanan Mossel: Explicit Optimal Hardness via Gaussian stability results. CoRR abs/1202.5258 (2012)

Elchanan Mossel, Ariel D. Procaccia, Miklós Z. Rácz: A Smooth Transition from Powerlessness to Absolute Power. CoRR abs/1205.2074 (2012)

Elchanan Mossel, Joe Neeman, Omer Tamuz: Majority Dynamics and Aggregation of Information in Social Networks. CoRR abs/1207.0893 (2012)

Siu On Chan, Elchanan Mossel, Joe Neeman: On extracting common random bits from correlated sources on large alphabets. CoRR abs/1208.5946 (2012)

Elchanan Mossel, Allan Sly, Omer Tamuz: Strategic Learning and the Topology of Social Networks. CoRR abs/1209.5527 (2012)

Anindya De, Elchanan Mossel, Joe Neeman: Majority is Stablest : Discrete and SoS. CoRR abs/1211.1001 (2012)

Anindya De, Elchanan Mossel: Explicit Optimal hardness via Gaussian stability results. Electronic Colloquium on Computational Complexity (ECCC) 19: 16 (2012)

Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld, Elad Verbin: Sorting and Selection in Posets. SIAM J. Comput. 40(3): 597-622 (2011)

Constantinos Daskalakis, Elchanan Mossel, Sébastien Roch: Phylogenies without Branch Bounds: Contracting the Short, Pruning the Deep. SIAM J. Discrete Math. 25(2): 872-893 (2011)

Tamir Tuller, Elchanan Mossel: Co-evolution Is Incompatible with the Markov Assumption in Phylogenetics. IEEE/ACM Trans. Comput. Biology Bioinform. 8(6): 1667-1670 (2011)

Andrej Bogdanov, Elchanan Mossel: On Extracting Common Random Bits From Correlated Sources. IEEE Transactions on Information Theory 57(10): 6351-6355 (2011)

Nayantara Bhatnagar, Andrej Bogdanov, Elchanan Mossel: The Computational Complexity of Estimating MCMC Convergence Time. APPROX-RANDOM 2011: 424-435

Nathan Keller, Elchanan Mossel, Tomer Schlank: A Note on the Entropy/Influence Conjecture. CoRR abs/1105.2651 (2011)

Elchanan Mossel, Sébastien Roch, Allan Sly: Robust estimation of latent tree graphical models: Inferring hidden states with inexact parameters. CoRR abs/1109.4668 (2011)

Elchanan Mossel, Miklós Z. Rácz: A quantitative Gibbard-Satterthwaite theorem without neutrality. CoRR abs/1110.5888 (2011)

Jan Arpe, Elchanan Mossel: Application of a Generalization of Russo's Formula to Learning from Multiple Random Oracles. Combinatorics, Probability & Computing 19(2): 183-199 (2010)

Elchanan Mossel, Sébastien Roch: Submodularity of Influence in Social Networks: From Local to Global. SIAM J. Comput. 39(6): 2176-2188 (2010)

Elchanan Mossel, Sébastien Roch: Incomplete Lineage Sorting: Consistent Phylogeny Estimation from Multiple Loci. IEEE/ACM Trans. Comput. Biology Bioinform. 7(1): 166-171 (2010)

Marcus Isaksson, Guy Kindler, Elchanan Mossel: The Geometry of Manipulation: A Quantitative Proof of the Gibbard-Satterthwaite Theorem. FOCS 2010: 319-328

Elchanan Mossel, Grant Schoenebeck: Reaching Consensus on Social Networks. ICS 2010: 214-229

Elchanan Mossel, Omer Tamuz: Truthful Fair Division. SAGT 2010: 288-299

David Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos H. Papadimitriou, Michael Schapira, Yaron Singer, Christopher Umans: Inapproximability for VCG-Based Combinatorial Auctions. SODA 2010: 518-536

Elchanan Mossel, Omer Tamuz: Efficient Bayesian Learning in Social Networks with Gaussian Estimators. CoRR abs/1002.0747 (2010)

Elchanan Mossel, Omer Tamuz: Truthful Fair Division. CoRR abs/1003.5480 (2010)

Nayantara Bhatnagar, Andrej Bogdanov, Elchanan Mossel: The Computational Complexity of Estimating Convergence Time. CoRR abs/1007.0089 (2010)

Andrej Bogdanov, Elchanan Mossel: On extracting common random bits from correlated sources. CoRR abs/1007.2315 (2010)

Tamir Tuller, Elchanan Mossel: Co-evolution is Incompatible with the Markov Assumption in Phylogenetics. CoRR abs/1008.0322 (2010)

Per Austrin, Elchanan Mossel: Approximation Resistant Predicates from Pairwise Independence. Computational Complexity 18(2): 249-271 (2009)

Amin Coja-Oghlan, Elchanan Mossel, Dan Vilenchik: A Spectral Approach to Analysing Belief Propagation for 3-Colouring. Combinatorics, Probability & Computing 18(6): 881-912 (2009)

Elchanan Mossel, Allan Sly: Rapid mixing of Gibbs sampling on graphs that are sparse on average. Random Struct. Algorithms 35(2): 250-270 (2009)

Irit Dinur, Elchanan Mossel, Oded Regev: Conditional Hardness for Approximate Coloring. SIAM J. Comput. 39(3): 843-873 (2009)

Elchanan Mossel, Sébastien Roch, Mike A. Steel: Shrinkage Effect in Ancestral Maximum Likelihood. IEEE/ACM Trans. Comput. Biology Bioinform. 6(1): 126-133 (2009)

Constantinos Daskalakis, Elchanan Mossel, Sébastien Roch: Phylogenies without Branch Bounds: Contracting the Short, Pruning the Deep. RECOMB 2009: 451-465

Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld, Elad Verbin: Sorting and selection in posets. SODA 2009: 392-401

Elchanan Mossel: Arrow's Impossibility Theorem Without Unanimity. CoRR abs/0901.4727 (2009)

Elchanan Mossel, Christos H. Papadimitriou, Michael Schapira, Yaron Singer: VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension. CoRR abs/0905.1995 (2009)

Mark Braverman, Elchanan Mossel: Sorting from Noisy Information. CoRR abs/0910.1191 (2009)

Andrej Bogdanov, Elchanan Mossel, Salil P. Vadhan: The Complexity of Distinguishing Markov Random Fields. APPROX-RANDOM 2008: 331-342

Guy Bresler, Elchanan Mossel, Allan Sly: Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms. APPROX-RANDOM 2008: 343-356

Per Austrin, Elchanan Mossel: Approximation Resistant Predicates from Pairwise Independence. IEEE Conference on Computational Complexity 2008: 249-258

Elchanan Mossel: Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes. FOCS 2008: 156-165

Andrea Montanari, Elchanan Mossel: Smooth compression, Gallager bound and nonlinear sparse-graph codes. ISIT 2008: 2474-2478

Elchanan Mossel, Allan Sly: Rapid mixing of Gibbs sampling on graphs that are sparse on average. SODA 2008: 238-247

Mark Braverman, Elchanan Mossel: Noisy sorting without resampling. SODA 2008: 268-276

Per Austrin, Elchanan Mossel: Approximation Resistant Predicates From Pairwise Independence. CoRR abs/0802.2300 (2008)

Jan Arpe, Elchanan Mossel: Multiple Random Oracles Are Better Than One. CoRR abs/0804.3817 (2008)

Jan Arpe, Elchanan Mossel: Agnostically Learning Juntas from Random Walks. CoRR abs/0806.4210 (2008)

Per Austrin, Elchanan Mossel: Approximation Resistant Predicates From Pairwise Independence. Electronic Colloquium on Computational Complexity (ECCC) 15(009) (2008)

Elitza N. Maneva, Elchanan Mossel, Martin J. Wainwright: A new look at survey propagation and its generalizations. J. ACM 54(4) (2007)

Elchanan Mossel, Sébastien Roch: Slow emergence of cooperation for win-stay lose-shift on trees. Machine Learning 67(1-2): 7-22 (2007)

Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Jirí Matousek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, Emo Welzl: Online Conflict-Free Coloring for Intervals. SIAM J. Comput. 36(5): 1342-1359 (2007)

Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell: Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?. SIAM J. Comput. 37(1): 319-357 (2007)

Elchanan Mossel: Distorted Metrics on Trees and Phylogenetic Forests. IEEE/ACM Trans. Comput. Biology Bioinform. 4(1): 108-116 (2007)

Elchanan Mossel, Sébastien Roch: On the submodularity of influence in social networks. STOC 2007: 128-134

Mark Braverman, Elchanan Mossel: Noisy Sorting Without Resampling. CoRR abs/0707.1051 (2007)

Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld, Elad Verbin: Sorting and Selection in Posets. CoRR abs/0707.1532 (2007)

Amin Coja-Oghlan, Elchanan Mossel, Dan Vilenchik: A Spectral Approach to Analyzing Belief Propagation for 3-Coloring. CoRR abs/0712.0171 (2007)

Guy Bresler, Elchanan Mossel, Allan Sly: Reconstruction of Markov Random Fields from Samples: Some Easy Observations and Algorithms. CoRR abs/0712.1402 (2007)

Constantinos Daskalakis, Alexandros G. Dimakis, Elchanan Mossel: Connectivity and Equilibrium in Random Games. CoRR abs/math/0703902 (2007)

Elchanan Mossel, Amir Shpilka, Luca Trevisan: On epsilon-biased generators in NC⁰. Random Struct. Algorithms 29(1): 56-81 (2006)

Uriel Feige, Elchanan Mossel, Dan Vilenchik: Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems. APPROX-RANDOM 2006: 339-350

Christian Borgs, Jennifer T. Chayes, Elchanan Mossel, Sébastien Roch: The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels. FOCS 2006: 518-530

Constantinos Daskalakis, Cameron Hill, Alexander Jaffe, Radu Mihaescu, Elchanan Mossel, Satish Rao: Maximal Accurate Forests from Distance Matrices. RECOMB 2006: 281-295

Constantinos Daskalakis, Elchanan Mossel, Sébastien Roch: Optimal phylogenetic reconstruction. STOC 2006: 159-168

Irit Dinur, Elchanan Mossel, Oded Regev: Conditional hardness for approximate coloring. STOC 2006: 344-353

Elchanan Mossel, Yuval Peres: New Coins From Old: Computing With Unknown Bias. Combinatorica 25(6): 707-724 (2005)

Nader H. Bshouty, Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio: Learning DNF from random walks. J. Comput. Syst. Sci. 71(3): 250-265 (2005)

Elchanan Mossel, Ryan O'Donnell: Coin flipping from a cosmic source: On error correction of truly random bits. Random Struct. Algorithms 26(4): 418-436 (2005)

Elchanan Mossel, Ryan O'Donnell, Krzysztof Oleszkiewicz: Noise stability of functions with low in.uences invariance and optimality. FOCS 2005: 21-30

Amos Fiat, Meital Levy, Jirí Matousek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, Emo Welzl: Online conflict-free coloring for intervals. SODA 2005: 545-554

Elitza N. Maneva, Elchanan Mossel, Martin J. Wainwright: A new look at survey propagation and its generalizations. SODA 2005: 1089-1098

Elchanan Mossel, Sébastien Roch: Learning nonsingular phylogenies and hidden Markov models. STOC 2005: 366-375

Elchanan Mossel, Sébastien Roch: Learning nonsingular phylogenies and hidden Markov models. CoRR abs/cs/0502076 (2005)

Irit Dinur, Elchanan Mossel, Oded Regev: Conditional Hardness for Approximate Coloring. CoRR abs/cs/0504062 (2005)

Elchanan Mossel, Ryan O'Donnell, Krzysztof Oleszkiewicz: Noise stability of functions with low influences: invariance and optimality. CoRR abs/math/0503503 (2005)

Irit Dinur, Elchanan Mossel, Oded Regev: Conditional Hardness for Approximate Coloring. Electronic Colloquium on Computational Complexity (ECCC)(039) (2005)

Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel: Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? Electronic Colloquium on Computational Complexity (ECCC)(101) (2005)

Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio: Learning functions of k relevant variables. J. Comput. Syst. Sci. 69(3): 421-434 (2004)

Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell: Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? FOCS 2004: 146-154

Elchanan Mossel, Yuval Peres, Alistair Sinclair: Shuffling by Semi-Random Transpositions. FOCS 2004: 572-581

Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, Amin Saberi: On approximately fair allocations of indivisible goods. ACM Conference on Electronic Commerce 2004: 125-131

Elitza N. Maneva, Elchanan Mossel, Martin J. Wainwright: A New Look at Survey Propagation and its Generalizations. CoRR cs.CC/0409012 (2004)

Elchanan Mossel: On the Impossibility of Reconstructing Ancestral Data and Phylogenies. Journal of Computational Biology 10(5): 669-676 (2003)

Elchanan Mossel, Ryan O'Donnell: On the noise sensitivity of monotone functions. Random Struct. Algorithms 23(3): 333-350 (2003)

Elchanan Mossel, Amir Shpilka, Luca Trevisan: On e-Biased Generators in NC0. FOCS 2003: 136-145

Nader H. Bshouty, Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio: Learning DNF from Random Walks. FOCS 2003: 189-198

Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio: Learning juntas. STOC 2003: 206-212

Elchanan Mossel, Amir Shpilka, Luca Trevisan: On epsilon-Biased Generators in NC0. Electronic Colloquium on Computational Complexity (ECCC)(043) (2003)

Elchanan Mossel: The Minesweeper Game: Percolation And Complexity. Combinatorics, Probability & Computing 11(5): 487-499 (2002)

Elchanan Mossel, Christopher Umans: On the complexity of approximating the VC dimension. J. Comput. Syst. Sci. 65(4): 660-671 (2002)

Elchanan Mossel, Christopher Umans: On the Complexity of Approximating the VC Dimension. IEEE Conference on Computational Complexity 2001: 220-225

Claire Kenyon, Elchanan Mossel, Yuval Peres: Glauber Dynamics on Trees and Hyperbolic Graphs. FOCS 2001: 568-578

Itai Benjamini, Olle Häggström, Elchanan Mossel: On Random Graph Homomorphisms into Z. J. Comb. Theory, Ser. B 78(1): 86-114 (2000)

Johan Jonasson, Elchanan Mossel, Yuval Peres: Percolation in a dependent random environment. Random Struct. Algorithms 16(4): 333-343 (2000)

Elchanan Mossel: Recursive reconstruction on periodic trees. Random Struct. Algorithms 13(1): 81-97 (1998)