Eric Vigoda's Publication List

C. Carlson, and E. Vigoda. Flip Dynamics for Sampling Colorings: Improving (11/6−ε) Using a Simple Metric. Available on arXiv: https://arxiv.org/abs/2407.04870
C. Carlson, X. Chen, W. Feng, and E. Vigoda. Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree. Available on arXiv: https://arxiv.org/abs/2407.04576
D. Stefankovic, and E. Vigoda. Spectral Independence Lecture Notes. Available on arXiv: https://arxiv.org/abs/2307.13826, and see Summer School webpage.
C. Carlson, D. Frishberg, and E. Vigoda. Improved Distributed Algorithms for Random Colorings. OPODIS, 2023. arXiv:2309.07859
U. Hebert-Johnson, D. Lokshtanov, and E. Vigoda. Counting and Sampling Labeled Chordal Graphs in Polynomial Time. ESA, 2023. Best paper award. arXiv:2308.09703
C. Efthymiou, T. Hayes, D. Stefankovic, and E. Vigoda Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees. RANDOM, 2023. arXiv:2307.07727
A. Blanca, Z. Chen, D. Stefankovic, and E. Vigoda. Identity Testing for High-Dimensional Distributions via Entropy Tensorization. COLT, 2023. arXiv:2207.09102
A. Coja-Oghlan, A. Galanis, L.A. Goldberg, J.B. Ravelomanana, D. Stefankovic, and E. Vigoda. Metastability of the Potts ferromagnet on random regular graphs. ICALP, 2022. arXiv:2202.05777
A. Galanis, D. Stefankovic, and E. Vigoda. Approximating observables is as hard as counting. ICALP, 2022. arxiv:2206.11606
A. Blanca, P. Caputo, Z. Chen, D. Parisi, D. Stefankovic, and E. Vigoda. On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization. SODA, 2022. arXiv:2103.07459
Z. Chen, A. Galanis, D. Stefankovic, and E. Vigoda. Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region. SODA, 2022. arXiv:2105.01784
Z. Chen, K. Liu, and E. Vigoda. Spectral Independence via Stability and Applications to Holant-Type Problems. FOCS, 2021. arXiv:2106.03366
A. Blanca, Z. Chen, D. Stefankovic, and E. Vigoda. The Swendsen-Wang Dynamics on Trees. RANDOM, 2021. (arXiv)
Z. Chen, K. Liu, and E. Vigoda. Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion. STOC, 2021. (arXiv), Slides for RS&A talk
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. 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. COLT, 2019. (arXiv)
C. Efthymiou, A. Galanis, T. P. Hayes, D. Stefankovic, and E. Vigoda. Improved Strong Spatial Mixing for Colorings on Trees. 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. RANDOM, 2019. (arXiv)
A. Blanca, R. Gheissari, and E. Vigoda. Random-cluster dynamics in ℤ²: rapid mixing with general boundary conditions. RANDOM, 2019. (arXiv)
A. Blanca, Z. Chen, and E. Vigoda. Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region. 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. 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. Algorithmic Learning Theory (ALT), 2018. Best Paper award. (arXiv)
D. Stefankovic, E. Vigoda, and J. Wilmes. On Counting Perfect Matchings in General Graphs. LATIN, 2018. (arXiv)
A. Blanca, P. Caputo, A. Sinclair, and E. Vigoda. Spatial Mixing and Non-local Markov chains. SODA, 2018. (arXiv)
C. Efthymiou, T. P. Hayes, D. Stefankovic, and E. Vigoda. Sampling Random Colorings of Sparse Random Graphs. SODA, 2018. (arXiv)
S. Park, Y. Jang, A. Galanis, J. Shin, D. Stefankovic, and E. Vigoda. Rapid Mixing Swendsen-Wang Sampler for Stochastic Partitioned Attractive Models. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 440– 449, 2017. (arXiv)
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. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 704-713, 2016. (arXiv)
A. Galanis, D. Stefankovic, E. Vigoda, and L. Yang. Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results. SIAM Journal on Computing, 45-6:2004-2065, 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, 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.