PUBLICATIONS

• Reconstruction for Colorings on Trees
  N. Bhatnagar, J. Vera, E. Vigoda, and D. Weitz
  Preprint.
  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
  FOCS 2004.
  Download: PS or PDF
• 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.