Showing 2022Show all
3 papers · 1 filter
cs.DS2022
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…
cs.DS2022
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…
cs.DS2022
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…