5 papers
A Counting Lovász Local Lemma
Hongyang Liu, Chunyang Wang, Yitong Yin +2
We establish a counting analogue of the Lovász Local Lemma: we give polynomial-time algorithms for approximately counting satisfying assignments of general constraint satisfaction…
Work-Efficient Parallel Counting via Sampling
Hongyang Liu, Yitong Yin, Yiyao Zhang
A canonical approach to approximating the partition function of a Gibbs distribution via sampling is simulated annealing. This method has led to efficient reductions from counting…
Tight Bounds for Sampling q-Colorings via Coupling from the Past
Tianxing Ding, Hongyang Liu, Yitong Yin +1
The Coupling from the Past (CFTP) paradigm is a canonical method for perfect sampling. For uniform sampling of proper -colorings in graphs with maximum degree , the bounding…
Local Gibbs sampling beyond local uniformity
Hongyang Liu, Chunyang Wang, Yitong Yin
Local samplers are algorithms that generate random samples based on local queries to high-dimensional distributions, ensuring the samples follow the correct induced distributions w…
Phase Transitions via Complex Extensions of Markov Chains
Jingcheng Liu, Chunyang Wang, Yitong Yin +1
We study algebraic properties of partition functions, particularly the location of zeros, through the lens of rapidly mixing Markov chains. The classical Lee-Yang program initiated…