Eric Vigoda

Professor of Computer Science
Georgia Tech

Eric
Director, Algorithms & Randomness Center
Professor, School of Computer Science
Georgia Institute of Technology

Fulkerson Prize, 2006.
Machtey Award, 1999.
Ph.D., CS, UC Berkeley, 1999.
BS, Johns Hopkins, 1994.

Contact information
Office: Klaus 2222A

Main research interests:

  • Markov chain Monte Carlo (MCMC) methods
  • Randomized algorithms
  • Phase transitions in Statistical Physics
  • Markov chains in Evolutionary Biology

Semi-recent list of publications

  • C. Efthymiou, T. P. Hayes, D. Stefankovic, E. Vigoda, and Y. Yin. Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model. To appear in Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2016. (arXiv)
  • A. Galanis, D. Stefankovic, E. Vigoda, and L. Yang. Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results. To appear in SIAM Journal on Computing, 2016. (arXiv)
  • A. Galanis, D. Stefankovic, and E. Vigoda. Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models. Combinatorics, Probability & Computing, 25(4):500-559, 2016. (arXiv)
  • J.-Y. Cai, A. Galanis, L. A. Goldberg, H. Guo, M. Jerrum, D. Stefankovic, and E. Vigoda. #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region. Journal of Computer and System Sciences, 82(5):690-711, 2016. (arXiv)
  • A. Galanis, D. Stefankovic, and E. Vigoda. Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region. Journal of the ACM, 62(6): article no. 50, 2015. (arXiv)
  • J. C. Vera, E. Vigoda, and L. Yang. Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions. SIAM Journal on Discrete Mathematics, 29(4):1895-1915, 2015. (arXiv)
  • T. Hayes, J. Vera, and E. Vigoda. Randomly coloring planar graphs with fewer colors than the maximum degree. Random Structures and Algorithms, 47(4):731-759, 2015. (arXiv)
  • A. Galanis, D. Stefankovic, and E. Vigoda. Swendsen-Wang Algorithm on the Mean-Field Potts Model. In Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM), pages 815-828, 2015.(arXiv)
  • A. Galanis, D. Stefankovic, and E. Vigoda. Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages 823-831, 2014. (arXiv), (journal)
  • R. Restrepo, D. Stefankovic, J. C. Vera, E. Vigoda, and L. Yang. Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees. SIAM Journal on Discrete Mathematics, 28(2):835-861, 2014. (arXiv)
  • A. Galanis, Q. Ge, D. Stefankovic, E. Vigoda, and L. Yang. Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model. Random Structures and Algorithms, 45(1):78-110, 2014. (arXiv)
  • A. Galanis, D. Stefankovic, E. Vigoda, and L. Yang. Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results. In Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM), pages 677-691, 2014.
  • J.-Y. Cai, A. Galanis, L. A. Goldberg, H. Guo, M. Jerrum, D. Stefankovic, and E. Vigoda. #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region. In Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM), pages 582-595, 2014.
  • R. Restrepo, J. Shin, P. Tetali, E. Vigoda, and L. Yang. Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets. Probability Theory and Related Fields, 156(1-2):75-99, 2013. (arXiv)
  • J. C. Vera, E. Vigoda, and L. Yang. Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions. In Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM), pages 699-713, 2013.
  • M. Dyer, A. Frieze, T. Hayes, and E. Vigoda. Randomly Coloring Constant Degree Graphs. Random Structures and Algorithms, 43(2):181-200, 2013.
  • P. Tetali, J. C. Vera, E. Vigoda and L. Yang. Phase Transition for the Mixing Time of the Glauber Dynamics for Coloring Regular Trees. Annals of Applied Probability, 22(6):2210-2239, 2012.
  • D. Stefankovic, S. Vempala, and E. Vigoda. A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions. SIAM Journal on Computing, 41(2):356-366, 2012.
  • I. Bezakova, A. Sinclair, D. Stefankovic, and E. Vigoda. Negative Examples for Sequential Importance Sampling of Binary Contingency Tables. Algorithmica, 64(4):606-620, 2012.
  • R. Restrepo, J. Shin, P. Tetali, E. Vigoda, and L. Yang. Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 140-149, 2011.
  • P. Gopalan, A. Klivans, R. Meka, D. Stefankovic, S. Vempala, and E. Vigoda. An FPTAS for #Knapsack and Related Counting Problems. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 817-826, 2011.
  • D. Stefankovic and E. Vigoda. Fast Convergence of MCMC Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species. SIAM Journal on Discrete Mathematics, 25(3):1194-1211, 2011.
  • N. Bhatnagar, J. Vera, E. Vigoda, and D. Weitz. Reconstruction for Colorings on Trees. SIAM Journal on Discrete Mathematics, 25(2):809-826, 2011.
  • A. Galanis, Q. Ge, D. Stefankovic, E. Vigoda, L. Yang. Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model. In Proceedings of the 15th International Workshop on Randomization and Computation (RANDOM), pages 567-578, 2011.
  • R. Restrepo, D. Stefankovic, J. C. Vera, E. Vigoda, and L. Yang. Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 945-956, 2011.
  • P. Tetali, J. C. Vera, E. Vigoda and L. Yang. Phase Transition for the Mixing Time of the Glauber Dynamics for Coloring Regular Trees. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1646-1656, 2010.
  • D. Stefankovic, S. Vempala, and E. Vigoda. Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting. Journal of the ACM, 56(3), article 18, 2009.
  • N. Elango, S.-H. Kim, NISC Comparative Sequencing Program, E. Vigoda, and S. V. Yi. Mutations of different molecular origins exhibit contrasting patterns of regional substitution rate variation. PLOS Computational Biology, 4(2):e1000015, 2008.
  • I. Bezakova, D. Stefankovic, V. Vazirani, and E. Vigoda. Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems. SIAM Journal on Computing, 37(5):1429-1454, 2008.
  • N. Bhatnagar, D. Randall, V. Vazirani and E. Vigoda. Random Bichromatic Matchings. Algorithmica, 50(4):418-445, 2008.
  • D. Stefankovic, S. Vempala, and E. Vigoda. Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting. In Proceedings of the 48th Symposium on Foundations of Computer Science (FOCS), pages 183-193, 2007.
  • T. Hayes, J. Vera, and E. Vigoda. Randomly coloring planar graphs with fewer colors than the maximum degree. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 450-458, 2007.
  • N. Bhatnagar, P. Caputo, P. Tetali, and E. Vigoda. Analysis of Top-Swap Shuffling for Genome Rearrangements. Annals of Applied Probability, 17(4):1424-1445, 2007.
  • D. Stefankovic and E. Vigoda. Phylogeny of Mixture Models: Robustness of Maximum Likelihood and Non-identifiable Distributions. Journal of Computational Biology, 14(2):144-155, 2007.
  • D. Stefankovic and E. Vigoda. Pitfalls of Heterogeneous Processes for Phylogenetic Reconstruction. Systematic Biology, 56(1):113-124, 2007.
  • I. Bezakova, N. Bhatnagar, and E. Vigoda. Sampling Binary Contingency Tables with a Greedy Start. Random Structures and Algorithms, 30(1-2):168-205, 2007.
  • T. Hayes and E. Vigoda. Variable Length Path Coupling. \emph{Random Structures and Algoithms, 31(3):251-272, 2007.
  • A. Frieze and E. Vigoda. Survey of Markov Chains for Randomly Sampling Colorings. In Combinatorics, Complexity and Chance: A Tribute to Dominic Welsh, Oxford University Press, eds. G. Grimmett and C. McDiarmid, 53-71, 2007.
  • S.-H. Kim, N. Elango, C. Warden, E. Vigoda and S. Yi. Heterogeneous genomic molecular clocks in primates. PLOS Genetics, 2(10): e163, 2006.
  • E. Mossel, and E. Vigoda. Limitations of Markov Chain Monte Carlo Algorithms for Bayesian Inference of Phylogeny, Annals of Applied Probability, 16(4): 2215-2234, 2006.
  • T. Hayes and E. Vigoda. Coupling with the Stationary Distribution and Improved Sampling for Colorings and Independent Sets. Annals of Applied Probability, 16(3): 1297-1318, 2006.
  • I. Bezakova, A. Sinclair, D. Stefankovic, and E. Vigoda. Negative Examples for Sequential Importance Sampling of Binary Contingency Tables. In Proceedings of the European Symposium on Algorithms (ESA), pages 136-147, 2006.
  • I. Bezakova, D. Stefankovic, V. Vazirani, and E. Vigoda. Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems, In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 900-907, 2006.
  • I. Bezakova, N. Bhatnagar, and E. Vigoda. Sampling Binary Contingency Tables with a Greedy Start, In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 414-423, 2006.
  • N. Bhatnagar, D. Randall, V. Vazirani, and E. Vigoda. Random Bichromatic Perfect Matchings. In Proceedings of the 7th Latin American Theoretical Informatics Symposium (LATIN), pages 190-201, 2006.
  • M. Dyer, A. Flaxman, A. Frieze, and E. Vigoda. Randomly Coloring Sparse Random Graphs with Fewer Colors than the Maximum Degree. Random Structures and Algorithms, 29(4): 450-465, 2006.
  • E. Mossel and E. Vigoda. Phylogenetic Markov Chain Monte Carlo Algorithms are Misleading on Mixtures of Trees. Science, 309:2207-2209, 2005.
  • T. Hayes and E. Vigoda. Coupling with the Stationary Distribution and Improved Sampling for Colorings and Independent Sets. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 971-979, 2005.
  • T. Łuczak and E. Vigoda. Torpid mixing for sampling colorings. Journal of Discrete Algorithms, 3(1):92-100, 2005.
  • M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. Journal of the ACM, 51(4):671-697, 2004. Winner of a Fulkerson Prize.
  • M. Dyer, A. Frieze, T. Hayes, and E. Vigoda. Randomly Coloring Constant Degree Graphs. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 582-589, 2004.
  • M. Dyer, A. Sinclair, E. Vigoda, and D. Weitz. Mixing in time and space for lattice spin systems: a combinatorial view. Random Structures and Algorithms, 24(4):461-479, 2004.
  • M. Jerrum, J-B. Son, P. Tetali, and E. Vigoda. Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains. Annals of Applied Probability, 14(4):1741-1765, 2004.
  • T. Hayes and E. Vigoda. Variable Length Path Coupling. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 96-103, 2004.
  • M. Dyer, M. Jerrum and E. Vigoda. Rapidly mixing Markov chains for dismantleable constraint graphs, {/it Graphs, morphisms and statistical physics, DIMACS series of the American Mathematical Society, 87-95, 2004.
  • T. Hayes and E. Vigoda. A Non-Markovian Coupling for Randomly Sampling Colorings, In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 618-627, 2003.
  • M. Dyer, A. Sinclair, E. Vigoda, and D. Weitz. Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View. In Proceedings of the 6th International Workshop on Randomization and Computation (RANDOM), pages 149-163, 2002.
  • M. Dyer, M. Jerrum, and E. Vigoda. Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs. Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View. In Proceedings of the 6th International Workshop on Randomization and Computation (RANDOM), pages 68-77, 2002.
  • M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pages 712-721, 2001.
  • E. Vigoda. A Note on the Glauber Dynamics for Sampling Independent Sets, Electronic Journal of Combinatorics, 8(1): Research paper 8, 2001.
  • E. Vigoda. Improved Bounds for Sampling Colorings. Journal of Mathematical Physics, 41(3):1555-1569, 2000.
  • E. Vigoda. Improved Bounds for Sampling Colorings. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS), pages 51-59, 1999. Winner of the Machtey award for best student paper.
  • C. Borgs, J. T. Chayes, A. Frieze, J-H. Kim, P. Tetali, E. Vigoda, and V. H. Vu. Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 218-229, 1999.
  • M. Luby, and E. Vigoda. Fast Convergence of the Glauber Dynamics for Sampling Independent Sets. Random Structures and Algorithms, 15(3-4):229-241, 1999.
  • M. Luby and E. Vigoda. Approximately Counting Up To Four. In Proceedings of the 29th annual ACM Symposium on Theory of Computing (STOC), pages 682-687, 1997.
  • A. Godbole, S. Thompson, and E. Vigoda. General upper bounds for covering numbers. Ars Combinatoria, 42:211-221, 1996.