6 papers · 1 filter
Optimal Simulated Annealing for Partition Function Estimation
Heng Guo, Hongyang Liu, Xiongxin Yang +2
In this note, we give a simple analysis of a non-adaptive simulated annealing algorithm for estimating the partition function of Gibbs distributions. This yields the most efficient…
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…
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…
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…