37 citations · 120 across the 35 of their papers we have counts for
38 papers
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…
Uniqueness and Rapid Mixing in the Bipartite Hardcore Model
Xiaoyu Chen, Jingcheng Liu, Yitong Yin
We characterize the uniqueness condition in the hardcore model for bipartite graphs with degree bounds only on one side, and provide a nearly linear time sampling algorithm that wo…
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…
Locally-iterative -Coloring in Sublinear (in ) Rounds
Xinyu Fu, Yitong Yin, Chaodong Zheng
Distributed graph coloring is one of the most extensively studied problems in distributed computing. There is a canonical family of distributed graph coloring algorithms known as t…
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…