Showing cs.DSShow all
3 papers · 1 filter
cs.DS2024
Counting and Sampling Labeled Chordal Graphs in Polynomial Time
Ursula Hebert-Johnson, Daniel Lokshtanov, Eric Vigoda
We present the first polynomial-time algorithm to exactly compute the number of labeled chordal graphs on vertices. Our algorithm solves a more general problem: given and $…
cs.DS2024
Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling
Antonio Blanca, Zongchen Chen, Daniel Å tefankoviÄ +1
We study the identity testing problem for high-dimensional distributions. Given as input an explicit distribution , an , and access to sampling oracle(s) for a h…
cs.DS2024
Spectral Independence via Stability and Applications to Holant-Type Problems
Zongchen Chen, Kuikui Liu, Eric Vigoda
This paper formalizes connections between stability of polynomials and convergence rates of Markov Chain Monte Carlo (MCMC) algorithms. We prove that if a (multivariate) partition…