Showing 2026Show all
3 papers · 1 filter
cs.DM2026
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…
cs.DS2026
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…
cs.CC2026
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…