☰

Eric Vigoda - Publications

Affiliations: 
University of Chicago, Chicago, IL 
Area:
Computer Science
Tree Info Similar researchers PubMed Report error

44 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2020 Blanca A, Galanis A, Goldberg LA, Štefankovič D, Vigoda E, Yang K. Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs Siam Journal On Discrete Mathematics. 34: 742-793. DOI: 10.1137/18M1219722  0.413
2020 Blanca A, Chen Z, Vigoda E. Swendsen‐Wang dynamics for general graphs in the tree uniqueness region Random Structures and Algorithms. 56: 373-400. DOI: 10.1002/Rsa.20858  0.36
2019 Efthymiou C, Hayes TP, Štefankovič D, Vigoda E, Yin Y. Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model Siam Journal On Computing. 48: 581-643. DOI: 10.1137/17M1127144  0.358
2019 Galanis A, Štefankovič D, Vigoda E. Swendsen‐Wang algorithm on the mean‐field Potts model Random Structures and Algorithms. 54: 82-147. DOI: 10.1002/Rsa.20768  0.441
2016 Galanis A, Štefankovič D, Vigoda E, Yang L. Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results Siam Journal On Computing. 45: 2004-2065. DOI: 10.1137/140997580  0.391
2016 GALANIS A, ŠTEFANKOVIČ D, VIGODA E. Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models Combinatorics Probability and Computing. 1-60. DOI: 10.1017/S0963548315000401  0.439
2015 Galanis A, Štefankovič D, Vigoda E. Swendsen-Wang algorithm on the mean-field Potts model Leibniz International Proceedings in Informatics, Lipics. 40: 815-828. DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.815  0.348
2015 Galanis A, Štefankovič D, Vigoda E. Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region Journal of the Acm. 62. DOI: 10.1145/2785964  0.382
2015 Hayes TP, Vera JC, Vigoda E. Randomly coloring planar graphs with fewer colors than the maximum degree Random Structures and Algorithms. 47: 731-759. DOI: 10.1002/Rsa.20560  0.439
2014 Restrepo R, Štefankovič D, Vera JC, Vigoda E, Yang L. Phase transition for glauber dynamics for independent sets on regular trees Siam Journal On Discrete Mathematics. 28: 835-861. DOI: 10.1137/120885498  0.397
2014 Cai JY, Galanis A, Goldberg LA, Guo H, Jerrum M, Štefankovič D, Vigoda E. #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region Journal of Computer and System Sciences. DOI: 10.1016/J.Jcss.2015.11.009  0.347
2014 Galanis A, Ge Q, Štefankovič D, Vigoda E, Yang L. Improved inapproximability results for counting independent sets in the hard-core model Random Structures and Algorithms. 45: 78-110. DOI: 10.1002/Rsa.20479  0.464
2013 Vera JC, Vigoda E, Yang L. Improved bounds on the phase transition for the hard-core model in 2-dimensions Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8096: 699-713. DOI: 10.1137/140976923  0.42
2013 Restrepo R, Shin J, Tetali P, Vigoda E, Yang L. Improved mixing condition on the grid for counting and sampling independent sets Probability Theory and Related Fields. 156: 75-99. DOI: 10.1007/S00440-012-0421-8  0.465
2012 Tetali P, Vera JC, Vigoda E, Yang L. Phase transition for the mixing time of the Glauber dynamics for coloring regular trees Annals of Applied Probability. 22: 2210-2239. DOI: 10.1214/11-Aap833  0.375
2012 Štefankovič D, Vempala S, Vigoda E. A deterministic polynomial-time approximation scheme for counting knapsack solutions Siam Journal On Computing. 41: 356-366. DOI: 10.1137/11083976X  0.454
2012 Bezáková I, Sinclair A, Stefankovic D, Vigoda E. Negative examples for sequential importance sampling of binary contingency tables Ivona Bezáková Algorithmica. 64: 606-620. DOI: 10.1007/S00453-011-9569-3  0.669
2011 Štefankovič D, Vigoda E. Fast convergence of Markov chain Monte Carlo algorithms for phylogenetic reconstruction with homogeneous data on closely related species Siam Journal On Discrete Mathematics. 25: 1194-1211. DOI: 10.1137/100790550  0.412
2011 Bhatnagar N, Juan V, Vigoda E, Weitz D. Reconstruction for colorings on trees Siam Journal On Discrete Mathematics. 25: 809-826. DOI: 10.1137/090755783  0.302
2011 Galanis A, Ge Q, Štefankovič D, Vigoda E, Yang L. Improved inapproximability results for counting independent sets in the hard-core model Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6845: 567-578. DOI: 10.1007/978-3-642-22935-0_48  0.364
2009 Stefankovic D, Vempala S, Vigoda E. Adaptive simulated annealing: A near-optimal connection between sampling and counting Journal of the Acm. 56. DOI: 10.1145/1516512.1516520  0.434
2008 Bhatnagar N, Randall D, Vazirani VV, Vigoda E. Random bichromatic matchings Algorithmica (New York). 50: 418-445. DOI: 10.1007/S00453-007-9096-4  0.413
2007 Stefankovic D, Vigoda E. Phylogeny of mixture models: robustness of maximum likelihood and non-identifiable distributions. Journal of Computational Biology : a Journal of Computational Molecular Cell Biology. 14: 156-89. PMID 17456014 DOI: 10.1089/Cmb.2006.0126  0.392
2007 Stefankovic D, Vigoda E. Pitfalls of heterogeneous processes for phylogenetic reconstruction. Systematic Biology. 56: 113-24. PMID 17366141 DOI: 10.1080/10635150701245388  0.341
2007 Bhatnagar N, Caputo P, Tetali P, Vigoda E. Analysis of top-swap shuffling for genome rearrangements Annals of Applied Probability. 17: 1424-1445. DOI: 10.1214/105051607000000177  0.333
2007 Frieze A, Vigoda E. A Survey on the Use of Markov Chains to Randomly Sample Colourings Combinatorics, Complexity, and Chance: a Tribute to Dominic Welsh. DOI: 10.1093/acprof:oso/9780198571278.003.0004  0.361
2006 Mossel E, Vigoda E. Limitations of markov chain Monte Carlo algorithms for bayesian inference of phylogeny Annals of Applied Probability. 16: 2215-2234. DOI: 10.1214/105051600000000538  0.408
2006 Bezáková I, Štefankovič D, Vazirani VV, Vigoda E. Accelerating simulated annealing for the permanent and combinatorial counting problems Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 900-907. DOI: 10.1137/050644033  0.684
2006 Mossel E, Vigoda E. Response to Comment on "Phylogenetic MCMC Algorithms Are Misleading on Mixtures of Trees" Science. 312: 367b-367b. DOI: 10.1126/Science.1124180  0.374
2006 Bezáková I, Bhatnagar N, Vigoda E. Sampling binary contingency tables with a greedy start Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 414-423. DOI: 10.1002/Rsa.V30:1/2  0.695
2006 Dyer M, Flaxman AD, Frieze AM, Vigoda E. Randomly coloring sparse random graphs with fewer colors than the maximum degree Random Structures and Algorithms. 29: 450-465. DOI: 10.1002/Rsa.V29:4  0.429
2006 Bezáková I, Bhatnagar N, Vigoda E. Sampling binary contingency tables with a greedy start Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 414-423.  0.47
2005 Mossel E, Vigoda E. Phylogenetic MCMC algorithms are misleading on mixtures of trees. Science (New York, N.Y.). 309: 2207-9. PMID 16195459 DOI: 10.1126/Science.1115493  0.435
2005 Hayes T, Vigoda E. Coupling with the stationary distribution and improved sampling for colorings and independent sets Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 971-979. DOI: 10.1214/105051606000000330  0.51
2005 Łuczak T, Vigoda E. Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings Journal of Discrete Algorithms. 3: 92-100. DOI: 10.1016/J.Jda.2004.05.002  0.536
2004 Jerrum M, Sinclair A, Vigoda E. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries Journal of the Acm. 51: 671-697. DOI: 10.1145/1008731.1008738  0.466
2004 Hayes TP, Vigoda E. Variable Length Path Coupling Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 15: 96-103. DOI: 10.1002/Rsa.V31:3  0.31
2004 Dyer M, Frieze A, Hayes TP, Vigoda E. Randomly coloring constant degree graphs Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 582-589. DOI: 10.1002/Rsa.20451  0.369
2003 Hayes TP, Vigoda E. A non-Markovian coupling for randomly sampling colorings Annual Symposium On Foundations of Computer Science - Proceedings. 618-627. DOI: 10.1109/SFCS.2003.1238234  0.315
2002 Dyer M, Jerrum M, Vigoda E. Rapidly mixing markov chains for dismantleable constraint graphs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2483: 68-77. DOI: 10.1007/3-540-45726-7_6  0.315
2001 Vigoda E. A note on the Glauber dynamics for sampling independent sets Electronic Journal of Combinatorics. 8: 1-8. DOI: 10.37236/1552  0.435
2001 Jerrum M, Sinclair A, Vigoda E. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 712-721.  0.327
2000 Vigoda E. Improved bounds for sampling colorings Journal of Mathematical Physics. 41: 1555-1569. DOI: 10.1063/1.533196  0.438
1999 Luby M, Vigoda E. Fast convergence of the glauber dynamics for sampling independent sets Random Structures and Algorithms. 15: 229-241. DOI: 10.1002/(Sici)1098-2418(199910/12)15:3/4<229::Aid-Rsa3>3.0.Co;2-X  0.457
Show low-probability matches.