# 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.