7 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…
Near-Optimal Parallel Approximate Counting via Sampling
David G. Harris, Vladimir Kolmogorov, Hongyang Liu +2
The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sa…
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…
Approximating the total variation distance between spin systems
Weiming Feng, Hongyang Liu, Minji Yang
Spin systems form an important class of undirected graphical models. For two Gibbs distributions and induced by two spin systems on the same graph , we study…