PUBLICATIONS

• Phase Transition for the Mixing Time of the Glauber Dynamics for Coloring Regular Trees
  P. Tetali, J. C. Vera, E. Vigoda and L. Yang
  To appear in SODA 2010.
  Download from arXiv
• Reconstruction for Colorings on Trees
  N. Bhatnagar, J. Vera, E. Vigoda, and D. Weitz
  To appear in SIAM Journal of Discrete Mathematics.
  Download from arXiv
• Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting
  D. Stefankovic, S. Vempala, and E. Vigoda
  FOCS 2007.
  Download full version from arXiv
• Randomly coloring planar graphs with fewer colors than the maximum degree.
  T. Hayes, J. Vera and E. Vigoda.
  STOC 2007.
  Download full version from arXiv
• Pitfalls of Heterogeneous Processes for Phylogenetic Reconstruction
  D. Stefankovic and E. Vigoda
  Systematic Biology 56(1): 113-124, 2007.
  Download: PDF
• Phylogeny of Mixture Models: Robustness of Maximum Likelihood and Non-identifiable Distributions
  D. Stefankovic and E. Vigoda
  Journal of Computational Biology 14(2): 156-189, 2007.
  Download from arXiv
  
• Heterogeneous Genomic Molecular Clocks in Primates
  S-H. Kim, N. Elango, C. Warden, E. Vigoda, and S. Yi
  PLOS Genetics, October 2006, 2(10), paper e163.
  Download: Open access on PLOS Genetics
• Mutations of Different Molecular Origins Exhibit Contrasting Patterns of Regional Substitution Rate Variation
  N. Elango, S-H. Kim, NISC Comparative Sequencing Program, E. Vigoda, and S. Yi
  PLOS Computational Biology, 4(2):e1000015, 2008.
  Download: Open access on PLOS Computational Biology
• Analysis of Top-Swap Shuffling for Genome Rearrangements
  N. Bhatnagar, P. Caputo, P. Tetali, and E. Vigoda
  Annals of Applied Probability, 17(4):1424-1445, 2007.
  Download from arXiv
• Negative Examples for Sequential Importance Sampling of Binary Contingency Tables
  I. Bezakova, A. Sinclair, D. Stefankovic, and E. Vigoda
  Submitted.
  Download from arXiv
  
• Phylogenetic MCMC Algorithms are Misleading on Mixtures of Trees
  E. Mossel and E. Vigoda
  Science, September 30, 2005, 309:2207-2209.
  Download paper
• Limitations of Markov Chain Monte Carlo Algorithms for Bayesian Inference of Phylogeny.
  E. Mossel and E. Vigoda
  Annals of Applied Probability 16(4): 2215-2234, 2006.
  Download from arXiv.
• A Survey on the use of Markov Chains to Randomly Sample Colorings
  A. Frieze and E. Vigoda
  In Combinatorics, Complexity and Chance, Oxford University Press, 2007.
  Download: PDF
• Random Bichromatic Matchings.
  N. Bhatnagar, D. Randall, V. Vazirani and E. Vigoda
  Algorithmica, 50(4):418-445, 2008. Preliminary version appears in LATIN 2006.
  Download: PS
• Sampling Binary Contingency Tables with a Greedy Start.
  I. Bezakova, N. Bhatnagar, and E. Vigoda
  Random Structures and Algorithms, 30(1-2):168-205, 2007.
  Preliminary version in SODA 2006.
  Download: PDF (Short SODA version: PDF)
• Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems.
  I. Bezakova, D. Stefankovic, V. Vazirani, and E. Vigoda
  SIAM Journal of Computing, 37(5):1429-1454, 2008.
  Preliminary version in SODA 2006.
  Download: PDF (Short SODA version: PDF)
• Randomly Coloring Sparse Random Graphs with Fewer Colors than the Maximum Degree.
  M. Dyer, A. Flaxman, A. Frieze, and E. Vigoda
  Random Structures and Algorithms, 29(4):450-465, 2006.
  Download: PDF
• Coupling with the Stationary Distribution and Improved Sampling for Colorings and Independent Sets.
  T. Hayes, and E. Vigoda
  Annals of Applied Probability, 16(4):1297-1318, 2006.
  Preliminary version appears in SODA 2005.
  Download: PDF
  
• Randomly coloring constant degree graphs.
  M. Dyer, A. Frieze, T. Hayes, and E. Vigoda
  Preliminary version in FOCS 2004.
  Full version submitted to Random Structures and Algorithms.
  Download: PDF
  And PDF copy of [7] T. P. Hayes, Uniformity Properties for Glauber Dynamics on Graph Colorings.
• Variable Length Path Coupling.
  T. Hayes and E. Vigoda
  Random Structures and Algorithms, 31(3):251-272, 2007.
  Preliminary version appears in SODA 2004.
  Download: PDF
• A Non-Markovian Coupling for Randomly Sampling Colorings.
  T. Hayes and E. Vigoda
  Preliminary version appears in FOCS 2003.
  Download: PDF
• A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries.
  M. Jerrum, A. Sinclair, and E. Vigoda
  In Journal of the ACM, 51(4):671-697, 2004.
  A preliminary version appears in STOC 2001.
  Fulkerson prize, 2006.
  Download: PDF
• Elementary bounds on Poincare and log-Sobolev constants for decomposable Markov chains.
  M. Jerrum, P. Tetali, J-B. Son, and E. Vigoda
  Annals of Applied Probability, 14(4):1741-1765, 2004.
  Download: PDF
• Mixing in time and space for lattice spin systems: A combinatorial view.
  M. Dyer, A. Sinclair, E. Vigoda, and D. Weitz
  Random Structures and Algorithms, 24(4):461-479, 2004.
  Preliminary version appears in RANDOM 2002.
  Download: PS
  
• Rapidly mixing Markov chains for dismantleable constraint systems.
  M. Dyer, M. Jerrum, and E. Vigoda
  In DIMACS Series of the AMS, 2004.
  Preliminary version appears in RANDOM 2002.
  Download: PS
• A note on the Glauber dynamics for sampling independent sets.
  E. Vigoda
  Electronic Journal of Combinatorics, 8(1), Research paper 8, 2001.
  Download: PS
• Torpid mixing of the Wang-Swendsen-Kotecky algorithm for sampling colorings.
  T. Luczak, and E. Vigoda
  Journal of Discrete Algorithms, 3(1):92-100, 2005.
  Download: PS
• Improved bounds for sampling colorings.
  E. Vigoda
  Journal of Mathematical Physics, 41(3):1555-1569, 2000.
  A preliminary version appears in FOCS 1999.
  Machtey award co-winner for best student paper at FOCS 1999.
  Download: PS
• A note on the Glauber dynamics for sampling independent sets.
  E. Vigoda
  Electronic Journal of Combinatorics, 8(1), Research paper 8, 2001.
  Download: PS
• Fast convergence of the Glauber dynamics for sampling independent sets.
  M. Luby and E. Vigoda
  Random Structures and Algorithms, 15(3-4):229-241, 1999.
• Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics
  C. Borgs, J. T. Chayes, J-H. Kim, A. Frieze, P. Tetali, E. Vigoda, and V. H. Vu
  FOCS 1999.
  Download: PDF
• Approximately Counting up to Four.
  M. Luby and E. Vigoda
  STOC 1997.
• General upper bounds for covering numbers
  A. P. Godbole, S. E. Thompson, and E. Vigoda
  Ars Combinatoria, 42, 1996.