Faculty Publications - Elchanan Mossel

Book chapters or sections

• A. Bogdanov, E. Mossel, and S. Vadhan, "The complexiity of distinguishing Markov random fields," in Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, A. Goel, K. Jansen, J. D. P. Rolim, and R. Rubinfeld, Eds., Lecture Notes in Computer Science, Vol. 5171, Berlin, Germany: Springer-Verlag, 2008, pp. 331-342.
• G. Bresler, E. Mossel, and A. sly, "Reconstruction of Markov random fields from samples: Some easy observations and algorithms," in Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, A. Goel, K. Jansen, J. D. P. Rolim, and R. Rubinfeld, Eds., Lecture Notes in Computer Science, Vol. 5171, Berlin, Germany: Springer-Verlag, 2008, pp. 343-356.
• U. Feige, E. Mossel, and D. Vilenchik, "Complete convergence of message passing algorithms for some satisfiability problems," in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, J. Diaz, K. Jansen, J. D. P. Rolim, and U. Zwick, Eds., Lecture Notes in Computer Science, Vol. 4110, Berlin, Germany: Springer-Verlag, 2006, pp. 339-350.
• C. Daskalakis, C. Hill, A. Jaffe, R. Mihaescu, E. Mossel, and S. Rao, "Maximal accurate forests from distance matrices," in Research in Computational Molecular Biology: Proc. 10th Annual Intl. Conf. (RECOMB 2006), A. Apostolico, C. Guerra, S. Istrail, P. Pevzner, and M. Waterman, Eds., Lecture Notes in Bioinformatics, Vol. 3909, Berlin, Germany: Springer-Verlag, 2006, pp. 281-295.
• E. Mossel and M. Steel, "How Much Can Evolved Characters Tell Us About The Tree That Generated Them?," in Mathematics of Evolution and Phylogeny, O. Gascuel, Ed., 1 ed., Oxford, UK: Oxford University Press, 2005, pp. 384-412.
• E. Mossel, "Survey: Information flow on trees," in Graphs, Morphisms and Statistical Physics: Proc. DIMACS/MIMATIA Workshop, J. Nesetril and P. Winkler, Eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 63, Providence, RI: American Mathematical Society, 2004, pp. 155-170.

Articles in journals or magazines

• M. Braverman, O. Etesami, and E. Mossel, "Mafia: A theoretical study of players and coalitions in a partial information environment," Annals of Applied Probability, vol. 18, no. 3, pp. 825-846, 2008.
• F. A. Matsen, E. Mossel, and M. Steel, "Mixed-up trees: The structure of phylogenetic mixtures," Bulletin of Mathematical Biology, vol. 70, no. 4, pp. 1115-1139, May 2008.
• S. Khot, G. Kindler, E. Mossel, and R. O'Donnell, "Optimal inapproximability for MAX-CUT and other 2-variable CSPs?," SIAM J. Computing, vol. 37, no. 1, pp. 319-357, 2007.
• E. Maneva, E. Mossel, and M. Wainwright, "A new look at survey propagation and its generalizations," J. ACM, vol. 54, no. 4, pp. 17, July 2007.
• E. Mossel and S. Roch, "Slow emergence of cooperation for win-stay lose-shift on trees," Machine Learning, vol. 62, no. 1-2, pp. 7-22, May 2007.
• E. Mossel, "Distorted metrics on trees and phylogenetic forests," IEEE/ACM Trans. Computational Biology and Informatics, vol. 4, no. 1, pp. 108-116, Jan. 2007.
• E. Mossel and E. Vigoda, "Limitations of Markov chain Monte Carlo algorithms for Bayesian inference of phylogeny," Annals of Applied Probability, vol. 16, no. 4, pp. 2215-2234, 2006.
• E. Mossel and S. Roch, "Learning nonsingular phylogenies and hidden Markov models," Annals of Applied Probability, vol. 16, no. 2, pp. 583-614, 2006.
• K. Chen, A. Fiat, H. Kaplan, M. Levy, J. Matousek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner, and E. Welzl, "Online conflict-free coloring for intervals," SIAM J. Computing, vol. 36, no. 5, pp. 1342-1359, 2006.
• E. Mossel, R. O'Donnell, O. Regev, J. E. Steif, and B. Sudakov, "Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality," Israel J. Mathematics, vol. 154, no. 1, pp. 299-336, Dec. 2006.
• E. Mossel, A. Shpilka, and L. Trevisan, "On epsilon-based generators in NC^0," Random Structures and Algorithms, vol. 29, no. 1, pp. 56-81, Aug. 2006.
• O. Haggstrom, G. Kalai, and E. Mossel, "A law of large numbers for weighted majority," Advances in Applied Mathematics, vol. 37, no. 1, pp. 112-123, July 2006.
• E. Mossel and E. Vigoda, "Response to Comment on "Phylogenetic MCMC Algorithms Are Misleading on Mixtures of Trees"," Science, vol. 312, no. 5772, pp. 367-367, April 2006.
• E. Mossel and Y. Peres, "New coins from old: Computing with unknown bias," Combinatorica, vol. 25, no. 6, pp. 707-724, Dec. 2005.
• N. H. Bshouty, E. Mossel, R. O'Donnell, and R. A. Servedio, "Learning DNF from random walks," J. Computer and System Sciences, vol. 71, no. 3, pp. 250-265, Oct. 2005.
• E. Mossel and E. Vigoda, "Phylogenetic MCMC are misleading on mixtures of trees (Short Report)," Science, vol. 309, no. 5744, pp. 2207-2209, Sep. 2005.
• E. Mossel and R. O'Donnell, "Coin flipping from a cosmic source: On error correction of truly random bits," Random Structures and Algorithms, vol. 26, no. 4, pp. 418-436, July 2005.
• E. Mossel and M. Steel, "Random biochemical networks: The probability of self-sustaining autocatalysis," J. Theoretical Biology, vol. 233, no. 3, pp. 327-336, April 2005.
• I. Benjamini, N. Berger, C. Hoffman, and E. Mossel, "Mixing times of the biased card shuffling and the asymmetric exclusion process," Trans. American Mathematical Society, vol. 357, no. 8, pp. 3013-3029, March 2005.
• N. Berger, C. Kenyon, E. Mossel, and Y. Peres, "Glauber dynamics on trees and hyperbolic graphs," Probability Theory and Related Fields, vol. 131, no. 3, pp. 311-340, March 2005.
• E. Mossel, R. O'Donnell, and R. A. Servedio, "Learning functions of k relevant variables," J. Computer and System Sciences, vol. 69, no. 3, pp. 421-434, Nov. 2004.
• S. Janson and E. Mossel, "Robust reconstruction on trees is determined by the second eigenvalue," Annals of Probability, vol. 32, no. 3B, pp. 2630-2649, July 2004.
• E. Mossel, "Phase transitions in phylogeny," Trans. American Mathematical Society, vol. 356, no. 6, pp. 2379-2404, June 2004.
• E. Mossel and M. Steel, "A phase transition for a random cluster model on phylogenetic trees," Mathematical Biosciences, vol. 187, no. 2, pp. 189-203, Feb. 2004.

Articles in conference proceedings

• E. Mossel, "Gaussian bounds for noise correlation of functions and tight analysis of long codes," in Proc. 49th Annual IEEE Symp. on Foundations of Computer Science (FOCS 2008), Los Alamitos, CA: IEEE Computer Society, 2008, pp. 156-165.
• A. Montanari and E. Mossel, "Smooth compression, Gallager bound and nonlinear sparse-graph codes," in Proc. 2008 IEEE Intl. Symp. on Information Theory (ISIT '08), Piscataway, NJ: IEEE Press, 2008, pp. 2474-2478.
• P. Austrin and E. Mossel, "Approximation resistant predicates from pairwise independence," in Proc. 23rd Annual IEEE Conf. on Computational Complexity (CCC 2008), Los Alamitos, CA: IEEE Computer Society, 2008, pp. 249-258.
• E. Mossel and A. Sly, "Rapid mixing of Gibbs sampling on graphs that are sparse on average," in Proc. 19th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2008), Philadelphia, PA: Society for Industrial and Applied Mathematics, 2008, pp. 238-247.
• M. Braverman and E. Mossel, "Noisy sorting without resampling," in Proc. 19th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2008), Philadelphia, PA: Society for Industrial and Applied Mathematics, 2008, pp. 268-276.
• E. Mossel and S. Roch, "On the submodularity of influence in social networks," in Proc. 39th Annual ACM Symp. on Theory of Computing (STOC 2007), New York, NY: The Association for Computing Machinery, Inc., 2007, pp. 128-134.
• C. Borgs, J. Chayes, E. Mossel, and S. Roch, "The Kesten-Stigum reconstruction bound is tight for roughly symmetric binary channels," in Proc. 47th Annual IEEE Symp. on Foundations of Computer Science (FOCS 2006), Los Alamitos, CA: IEEE Computer Society, 2006, pp. 518-530.
• C. Daskalakis, E. Mossel, and S. Roch, "Optimal phylogenetic reconstruction," in Proc. 38th Annual ACM Symp. on Theory of Computing (STOC 2006), New York, NY: The Association for Computing Machinery, Inc., 2006, pp. 159-168.
• I. Dinur, E. Mossel, and O. Regev, "Conditional hardness for approximate coloring," in Proc. 38th Annual ACM Symp. on Theory of Computing (STOC 2006), New York, NY: The Association for Computing Machinery, Inc., 2006, pp. 344-353.
• E. Mossel, R. O'Donnell, and K. Oleszkiewicz, "Noise stability of functions with low influences: Invariance and optimality," in Proc. 46th Annual IEEE Symp. on Foundations of Computer Science (FOCS 2005), Los Alamitos, CA: IEEE Computer Society, 2005, pp. 21-30.
• E. Mossel and S. Roch, "Learning nonsingular phylogenies and hidden Markov models," in Proc. 37th Annual ACM Symp. on Theory of Computing (STOC 2005), New York, NY: The Association for Computing Machinery, Inc., 2005, pp. 366-375.
• E. Maneva, E. Mossel, and M. Wainwright, "A new look at survey propagation and its generalizations (Extended Abstract)," in Proc. 16th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2005), Philadelphia, PA: Society for Industrial and Applied Mathematics, 2005, pp. 1089-1098.
• A. Fiat, M. Levy, J. Matousek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner, and E. Welzl, "Online conflict-free coloring for intervals," in Proc. 16th Annual ACM-SIAM Symp. on Discrete Algorithms, Philadelphia, PA: Society for Industrial and Applied Mathematics, 2005, pp. 545-554.
• E. N. Maneva, E. Mossel, and M. Wainwright, "A new look at survey propagation and its generalizations," in Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), SIAM, 2005, pp. 1089-1098.
• S. Khot, G. Kindler, E. Mossel, and R. O'Donnell, "Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?," in Proc. 45th Annual IEEE Symp. on Foundations of Computer Science (FOCS 2004), Los Alamitos, CA: IEEE Computer Society, 2004, pp. 146-154.
• E. Mossel, Y. Peres, and A. Sinclair, "Shuffling by semi-random transpositions," in Proc. 45th Annual IEEE Symp. on Foundations of Computer Science (FOCS 2004), Los Alamitos, CA: IEEE Computer Society, 2004, pp. 572-581.
• R. Lipton, E. Markakis, E. Mossel, and A. Saberi, "On approximately fair allocations of indivisible goods," in Proc. 5th ACM Conf. on Electronic Commerce (EC-2004), New York, NY: The Association for Computing Machinery, Inc., 2004, pp. 125-131.
• N. Bshouty, E. Mossel, R. O'Donnell, and R. A. Servedio, "Learning DNF from random walks," in Proc. 44th Annual IEEE Symp. on Foundations of Computer Science (FOCS 2003), Los Alamitos, CA: IEEE Computer Society, 2003, pp. 189-198.

Technical Reports

• E. Maneva, E. Mossel, and M. Wainwright, "A New Look at Survey Propagation and Its Generalizations," UC Berkeley, Department of Statistics, Tech. Rep. UCB/STAT-04-669, Sep. 2004.