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.
Z. Chen, K. Liu, and E. Vigoda.
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion.
STOC, 2021.
(arXiv)
A. Blanca, P. Caputo, D. Parisi, A. Sinclair, and E. Vigoda.
Entropy decay in the Swendsen-Wang dynamics.
STOC, 2021.
(arXiv)
Z. Chen, A. Galanis, D. Stefankovic, and E. Vigoda.
Rapid Mixing for Colorings via Spectral Independence.
SODA, 2021.
(arXiv)
Z. Chen, K. Liu, and E. Vigoda.
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction.
FOCS, 2020.
(arXiv)
A. Galanis, D. Stefankovic, and E. Vigoda.
The complexity of approximating averages on bounded-degree graphs.
FOCS, 2020. (arXiv)
A. Blanca, Z. Chen, D. Stefankovic, and E. Vigoda.
Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models.
In Proceedings of the Conference on Learning Theory (COLT), 2020.
(arXiv)
I. Bezakova, A. Blanca, Z. Chen, D. Stefankovic, and E. Vigoda.
Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models.
In Proceedings of the Conference on Learning Theory (COLT), 2019.
(arXiv)
C. Efthymiou, A. Galanis, T. P. Hayes, D. Stefankovic, and E. Vigoda.
Improved Strong Spatial Mixing for Colorings on Trees.
In Proceedings of the 23rd International Conference on Randomization and Computation (RANDOM), 2019.
(arXiv)
Z. Chen, A. Galanis, L. A. Goldberg, W. Perkins, J. Stewart, and E. Vigoda.
Fast algorithms at low temperatures via Markov chains.
In Proceedings of the 23rd International Conference on Randomization and Computation (RANDOM), 2019.
(arXiv)
A. Blanca, R. Gheissari, and E. Vigoda.
Random-cluster dynamics in ℤ2: rapid mixing with general boundary conditions.
In Proceedings of the 23rd International Conference on Randomization and Computation (RANDOM), 2019.
(arXiv)
A. Blanca, Z. Chen, and E. Vigoda.
Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region.
In Proceedings of the 22nd International Conference on Randomization and Computation (RANDOM), 2018.
(arXiv).
A. Blanca, A. Galanis, L. A. Goldberg, D. Stefankovic, E. Vigoda, K. Yang.
Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs.
In Proceedings of the 22nd International Conference on Randomization and Computation (RANDOM), 2018.
(arXiv).
M. E. Dyer, A. Galanis, L. A. Goldberg, M. Jerrum, and E. Vigoda.
Random Walks on Small World Networks.
ACM Transactions on Algorithms, 16(3):article 37, 2020.
(arXiv)
A. Blanca, Z. Chen, D. Stefankovic, and E. Vigoda.
Structure Learning of H-colorings.
In Proceedings of the 29th International Conference on Algorithmic Learning Theory (ALT),
2018. Best Paper award.
(arXiv)
D. Stefankovic, E. Vigoda, and J. Wilmes.
On Counting Perfect Matchings in General Graphs.
In Proceedings of the 13th Latin American
Theoretical Informatics Symposium (LATIN),
2018.
(arXiv)
A. Blanca, P. Caputo, A. Sinclair, and E. Vigoda.
Spatial Mixing and Non-local Markov chains.
In Proceedings of the 29th Annual ACM-SIAM
Symposium on Discrete Algorithms (SODA),
pages 1965-1980, 2018.
(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)
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.
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.
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.
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.
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. 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.
