5 citations · 26 across the 17 of their papers we have counts for
Showing 2020Show all
2 papers · 1 filter
cs.DS2020★ 2 cited
Sampling Constraint Satisfaction Solutions in the Local Lemma Regime
Weiming Feng, Kun He, Yitong Yin
We give a Markov chain based algorithm for sampling almost uniform solutions of constraint satisfaction problems (CSPs). Assuming a canonical setting for the Lovász local lemma, wh…
cs.DS2020★ 4 cited
Rapid mixing from spectral independence beyond the Boolean domain
Weiming Feng, Heng Guo, Yitong Yin +1
We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [ALO20]) from the Boolean domain to general discrete domains. This property characterises…