5 papers
Sampling Simultaneous Edge-Colorings
Ezra Furtado-Tiwari, Eric Vigoda
We study the sampling problem for simultaneous edge colorings. Given a pair of graphs and which are on the same vertex set , a simultaneous edge colo…
Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity
Vishesh Jain, Clayton Mizgerd, Eric Vigoda
Sampling graph colorings via local Markov chains is a central problem in approximate counting and Markov chain Monte Carlo (MCMC). We address the problem of sampling a random -c…
Critical window for approximate counting in dense Ising models
Andreas Galanis, Daniel Stefankovic, Eric Vigoda
We study the complexity of approximating the partition function of dense Ising models in the critical regime. Recent work of Chen, Chen, Yin, and Zhang (FOCS 2025) established fast…
Mixing of general biased adjacent transposition chains
Reza Gheissari, Holden Lee, Eric Vigoda
We analyze the general biased adjacent transposition shuffle process, which is a well-studied Markov chain on the symmetric group . In each step, an adjacent pair of elements…
Improved Distributed Algorithms for Random Colorings
Charlie Carlson, Daniel Frishberg, Eric Vigoda
We study distributed versions of Markov Chain Monte Carlo (MCMC) algorithms for generating random -colorings of an input graph with maximum degree . In the sequential settin…