2 papers
cs.DS2026
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…
cs.DS2025
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…