7 papers
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…
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…
A Sampling Lovász Local Lemma for Large Domain Sizes
Chunyang Wang, Yitong Yin
We present polynomial-time algorithms for approximate counting and sampling solutions to constraint satisfaction problems (CSPs) with atomic constraints within the local lemma regi…
Deterministic counting Lovász local lemma beyond linear programming
Kun He, Chunyang Wang, Yitong Yin
We give a simple combinatorial algorithm to deterministically approximately count the number of satisfying assignments of general constraint satisfaction problems (CSPs). Suppose t…
Towards derandomising Markov chain Monte Carlo
Weiming Feng, Heng Guo, Chunyang Wang +2
We present a new framework to derandomise certain Markov chain Monte Carlo (MCMC) algorithms. As in MCMC, we first reduce counting problems to sampling from a sequence of marginal…
Sampling Lovász Local Lemma For General Constraint Satisfaction Solutions In Near-Linear Time
Kun He, Chunyang Wang, Yitong Yin
We give a fast algorithm for sampling uniform solutions of general constraint satisfaction problems (CSPs) in a local lemma regime. Suppose that the CSP has variables with doma…