7 papers · 1 filter
A Counting and Sampling Lovász Local Lemma
Hongyang Liu, Chunyang Wang, Yitong Yin +2
We establish counting and sampling analogues of the Lovász Local Lemma: we give efficient algorithms for approximately counting and exactly sampling satisfying assignments of gener…
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…
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…
Efficient Parallel Ising Samplers via Localization Schemes
Xiaoyu Chen, Hongyang Liu, Yitong Yin +1
We introduce efficient parallel algorithms for sampling from the Gibbs distribution and estimating the partition function of Ising models. These algorithms achieve parallel efficie…
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 th…
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…