PUBLICATIONS:
-
Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
A. Galanis, D. Stefankovic, and E. Vigoda
Download from arXiv
-
Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets
R. Restrepo, J. Shin, P. Tetali, E. Vigoda, and L. Yang
To appear in Probability Theory and Related Fields.
Preliminary/short version appears in FOCS '11.
Download from arXiv
Associated datasets are available here.
-
Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model
A. Galanis, Q. Ge, D. Stefankovic, E. Vigoda, L. Yang
RANDOM 2011.
Download from arXiv
-
A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions
D. Stefankovic, S. Vempala, and E. Vigoda
SIAM Journal on Computing, 41(2):356-366, 2012.
Download from arXiv
Merge with
Gopalan-Klivans-Meka
appears in FOCS '11.
PDF of FOCS version.
-
Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees
R. Restrepo, D. Stefankovic, J. C. Vera, E. Vigoda, and L. Yang
SODA 2011.
Download from arXiv
-
Fast Convergence of Markov Chain Monte Carlo Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species
D. Stefankovic and E. Vigoda
SIAM Journal on Discrete Mathematics. 25(3):1194-1211, 2011.
PDF
-
Phase Transition for the Mixing Time of the Glauber Dynamics for Coloring
Regular Trees
P. Tetali, J. C. Vera, E. Vigoda and L. Yang
To appear in Annals of Applied Probability.
Preliminary/short version appears in SODA 2010.
Download from arXiv
-
Reconstruction for Colorings on Trees
N. Bhatnagar, J. Vera, E. Vigoda, and D. Weitz
SIAM Journal on Discrete Mathematics. 25(2):809-826, 2011.
Download from arXiv
-
Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting
D. Stefankovic, S. Vempala, and E. Vigoda
Journal of the ACM, 56(3):1-36, 2009.
A preliminary version appears in FOCS 2007.
Download full version from arXiv
-
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)
-
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
-
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
-
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
-
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
-
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)
-
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
-
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
-
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
-
Negative Examples for Sequential Importance Sampling of Binary Contingency Tables
I. Bezakova, A. Sinclair, D. Stefankovic, and E. Vigoda
To appear in Algorithmica.
Preliminary version appears in ESA 2006.
Download from arXiv
-
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.
-
Phylogenetic MCMC Algorithms are Misleading on Mixtures of Trees
E. Mossel and E. Vigoda
Science, September 30, 2005, 309:2207-2209.
Download paper
-
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
-
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
-
Randomly coloring constant degree graphs.
M. Dyer, A. Frieze, T. Hayes, and E. Vigoda
Submitted to Random Structures and Algorithms.
Preliminary version in FOCS 2004.
Download:
PDF
And
PDF copy of [7] T. P. Hayes, Uniformity Properties for
Glauber Dynamics on Graph Colorings.
-
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 Non-Markovian Coupling for Randomly
Sampling Colorings.
T. Hayes and E. Vigoda
Preliminary version appears in FOCS 2003.
Download:
PDF
-
A note on the Glauber dynamics for sampling independent sets.
E. Vigoda
Electronic Journal of Combinatorics, 8(1), Research paper 8, 2001.
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.
|