Eric Vigoda

Publication Activity (10 Years)

Years Active: 1996-2024
Publications (10 Years): 73

Top Venues

CoRR

APPROX-RANDOM

Random Struct. Algorithms

SODA

Publications

Charlie Carlson, Eric Vigoda
Flip Dynamics for Sampling Colorings: Improving (11/6-ε) Using a Simple Metric. CoRR (2024)
Charlie Carlson, Xiaoyu Chen, Weiming Feng, Eric Vigoda
Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree. CoRR (2024)
Úrsula Hébert-Johnson, Daniel Lokshtanov, Eric Vigoda
Counting and Sampling Labeled Chordal Graphs in Polynomial Time. ESA (2023)
Úrsula Hébert-Johnson, Daniel Lokshtanov, Eric Vigoda
Counting and Sampling Labeled Chordal Graphs in Polynomial Time. CoRR (2023)
Charlie Carlson, Daniel Frishberg, Eric Vigoda
Improved Distributed Algorithms for Random Colorings. CoRR (2023)
Daniel Stefankovic, Eric Vigoda
Spectral Independence Lecture Notes. CoRR (2023)
Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda
Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees. APPROX/RANDOM (2023)
Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda
Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling. COLT (2023)
Zongchen Chen, Kuikui Liu, Eric Vigoda
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction. SIAM J. Comput. 52 (1) (2023)
Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda
Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees. CoRR (2023)
Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda
The Swendsen-Wang dynamics on trees. Random Struct. Algorithms 62 (4) (2023)
Charlie Carlson, Daniel Frishberg, Eric Vigoda
Improved Distributed Algorithms for Random Colorings. OPODIS (2023)
Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Stefankovic, Eric Vigoda
On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization. SODA (2022)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Approximating observables is as hard as counting. CoRR (2022)
Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda
Identity Testing for High-Dimensional Distributions via Entropy Tensorization. CoRR (2022)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Approximating Observables Is as Hard as Counting. ICALP (2022)
Zongchen Chen, Kuikui Liu, Eric Vigoda
Spectral Independence via Stability and Applications to Holant-Type Problems. FOCS (2022)
Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Stefankovic, Eric Vigoda
Metastability of the Potts Ferromagnet on Random Regular Graphs. ICALP (2022)
Zongchen Chen, Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region. SODA (2022)
Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Stefankovic, Eric Vigoda
Metastability of the Potts ferromagnet on random regular graphs. CoRR (2022)
Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda
Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models. J. Mach. Learn. Res. 22 (2021)
Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Stefankovic, Eric Vigoda
On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization. CoRR (2021)
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins, James Stewart, Eric Vigoda
Fast algorithms at low temperatures via Markov chains. Random Struct. Algorithms 58 (2) (2021)
Zongchen Chen, Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Rapid Mixing for Colorings via Spectral Independence. SODA (2021)
Zongchen Chen, Kuikui Liu, Eric Vigoda
Spectral Independence via Stability and Applications to Holant-Type Problems. FOCS (2021)
Zongchen Chen, Kuikui Liu, Eric Vigoda
Spectral Independence via Stability and Applications to Holant-Type Problems. CoRR (2021)
Zongchen Chen, Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region. CoRR (2021)
Zongchen Chen, Kuikui Liu, Eric Vigoda
Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion. STOC (2021)
Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda
The Swendsen-Wang Dynamics on Trees. APPROX-RANDOM (2021)
Antonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair, Eric Vigoda
. STOC (2021)
Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda
Structure Learning of H-Colorings. ACM Trans. Algorithms 16 (3) (2020)
Zongchen Chen, Kuikui Liu, Eric Vigoda
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion. CoRR (2020)
Zongchen Chen, Kuikui Liu, Eric Vigoda
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction. FOCS (2020)
Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic, Eric Vigoda, Kuan Yang
Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs. SIAM J. Discret. Math. 34 (1) (2020)
Antonio Blanca, Zongchen Chen, Eric Vigoda
Swendsen-Wang dynamics for general graphs in the tree uniqueness region. Random Struct. Algorithms 56 (2) (2020)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
The complexity of approximating averages on bounded-degree graphs. FOCS (2020)
Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda
Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models. COLT (2020)
Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda
Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models. CoRR (2020)
Zongchen Chen, Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Rapid Mixing for Colorings via Spectral Independence. CoRR (2020)
Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda
The Swendsen-Wang Dynamics on Trees. CoRR (2020)
Ivona Bezáková, Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda
Lower Bounds for Testing Graphical Models: Colorings and Antiferromagnetic Ising Models. J. Mach. Learn. Res. 21 (2020)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
The complexity of approximating averages on bounded-degree graphs. CoRR (2020)
Martin E. Dyer, Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum, Eric Vigoda
Random Walks on Small World Networks. ACM Trans. Algorithms 16 (3) (2020)
Zongchen Chen, Kuikui Liu, Eric Vigoda
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction. CoRR (2020)
Antonio Blanca, Reza Gheissari, Eric Vigoda
: Rapid Mixing with General Boundary Conditions. APPROX-RANDOM (2019)
Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda, Yitong Yin
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model. SIAM J. Comput. 48 (2) (2019)
Ivona Bezáková, Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda
Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models. CoRR (2019)
Charilaos Efthymiou, Andreas Galanis, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda
Improved Strong Spatial Mixing for Colorings on Trees. CoRR (2019)
Charilaos Efthymiou, Andreas Galanis, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda
Improved Strong Spatial Mixing for Colorings on Trees. APPROX-RANDOM (2019)
Antonio Blanca, Pietro Caputo, Alistair Sinclair, Eric Vigoda
Spatial mixing and nonlocal Markov chains. Random Struct. Algorithms 55 (3) (2019)
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins, James Stewart, Eric Vigoda
Fast Algorithms at Low Temperatures via Markov Chains. APPROX-RANDOM (2019)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Swendsen-Wang algorithm on the mean-field Potts model. Random Struct. Algorithms 54 (1) (2019)
Ivona Bezáková, Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda
Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models. COLT (2019)
Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic, Eric Vigoda, Kuan Yang
Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs. CoRR (2018)
Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda
Sampling Random Colorings of Sparse Random Graphs. SODA (2018)
Antonio Blanca, Zongchen Chen, Eric Vigoda
Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region. APPROX-RANDOM (2018)
Antonio Blanca, Pietro Caputo, Alistair Sinclair, Eric Vigoda
Spatial Mixing and Non-local Markov chains. SODA (2018)
Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic, Eric Vigoda, Kuan Yang
Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs. APPROX-RANDOM (2018)
Antonio Blanca, Zongchen Chen, Eric Vigoda
Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region. CoRR (2018)
Daniel Stefankovic, Eric Vigoda, John Wilmes
On Counting Perfect Matchings in General Graphs. LATIN (2018)
Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda
Structure Learning of ${H}$-colorings. ALT (2018)
Antonio Blanca, Zongchen Chen, Daniel Stefankovic, Eric Vigoda
Structure Learning of H-colorings. CoRR (2017)
Sejun Park, Yunhun Jang, Andreas Galanis, Jinwoo Shin, Daniel Stefankovic, Eric Vigoda
Rapid Mixing Swendsen-Wang Sampler for Stochastic Partitioned Attractive Models. AISTATS (2017)
Daniel Stefankovic, Eric Vigoda, John Wilmes
On Counting Perfect Matchings in General Graphs. CoRR (2017)
Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda
Sampling Random Colorings of Sparse Random Graphs. CoRR (2017)
Martin E. Dyer, Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum, Eric Vigoda
Random Walks on Small World Networks. CoRR (2017)
Sejun Park, Yunhun Jang, Andreas Galanis, Jinwoo Shin, Daniel Stefankovic, Eric Vigoda
Rapid Mixing Swendsen-Wang Sampler for Stochastic Partitioned Attractive Models. CoRR (2017)
Antonio Blanca, Pietro Caputo, Alistair Sinclair, Eric Vigoda
Spatial Mixing and Non-local Markov chains. CoRR (2017)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda, Linji Yang
Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results. SIAM J. Comput. 45 (6) (2016)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models. Comb. Probab. Comput. 25 (4) (2016)
Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda, Yitong Yin
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model. CoRR (2016)
Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda, Yitong Yin
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model. FOCS (2016)
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, Eric Vigoda
#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. J. Comput. Syst. Sci. 82 (5) (2016)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Swendsen-Wang Algorithm on the Mean-Field Potts Model. CoRR (2015)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region. J. ACM 62 (6) (2015)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Swendsen-Wang Algorithm on the Mean-Field Potts Model. APPROX-RANDOM (2015)
Juan Carlos Vera, Eric Vigoda, Linji Yang
Improved Bounds on the Phase Transition for the Hard-Core Model in 2 Dimensions. SIAM J. Discret. Math. 29 (4) (2015)
Thomas P. Hayes, Juan Carlos Vera, Eric Vigoda
Randomly coloring planar graphs with fewer colors than the maximum degree. Random Struct. Algorithms 47 (4) (2015)
Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda, Linji Yang
Improved inapproximability results for counting independent sets in the hard-core model. Random Struct. Algorithms 45 (1) (2014)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda, Linji Yang
Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results. APPROX-RANDOM (2014)
Ricardo Restrepo, Daniel Stefankovic, Juan Carlos Vera, Eric Vigoda, Linji Yang
Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees. SIAM J. Discret. Math. 28 (2) (2014)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region. STOC (2014)
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, Eric Vigoda
#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region. APPROX-RANDOM (2014)
Juan Carlos Vera, Eric Vigoda, Linji Yang
Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions. APPROX-RANDOM (2013)
Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda
Randomly coloring constant degree graphs. Random Struct. Algorithms 43 (2) (2013)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
BIS-Hardness for Ferromagnetic Potts in the Ordered Phase and Related Results. CoRR (2013)
Juan Carlos Vera, Eric Vigoda, Linji Yang
Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions. CoRR (2013)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region CoRR (2013)
Ivona Bezáková, Alistair Sinclair, Daniel Stefankovic, Eric Vigoda
Negative Examples for Sequential Importance Sampling of Binary Contingency Tables. Algorithmica 64 (4) (2012)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models CoRR (2012)
Daniel Stefankovic, Santosh S. Vempala, Eric Vigoda
A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions. SIAM J. Comput. 41 (2) (2012)
Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda, Linji Yang
Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model. APPROX-RANDOM (2011)
Daniel Stefankovic, Eric Vigoda
Fast Convergence of Markov Chain Monte Carlo Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species. SIAM J. Discret. Math. 25 (3) (2011)
Ricardo Restrepo, Daniel Stefankovic, Juan Carlos Vera, Eric Vigoda, Linji Yang
Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees. SODA (2011)
Ricardo Restrepo, Jinwoo Shin, Prasad Tetali, Eric Vigoda, Linji Yang
Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets. FOCS (2011)
Parikshit Gopalan, Adam R. Klivans, Raghu Meka, Daniel Stefankovic, Santosh S. Vempala, Eric Vigoda
An FPTAS for #Knapsack and Related Counting Problems. FOCS (2011)
Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda, Linji Yang
Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model CoRR (2011)
Nayantara Bhatnagar, Juan Carlos Vera, Eric Vigoda, Dror Weitz
Reconstruction for Colorings on Trees. SIAM J. Discret. Math. 25 (2) (2011)
Ricardo Restrepo, Jinwoo Shin, Prasad Tetali, Eric Vigoda, Linji Yang
Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets CoRR (2011)
Daniel Stefankovic, Eric Vigoda
Fast Convergence of MCMC Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species CoRR (2010)

Eric Vigoda.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Eric Vigoda