4 citations · 12 across the 4 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
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…
cs.DS2019★ 3 cited
Fast sampling and counting k-SAT solutions in the local lemma regime
Weiming Feng, Heng Guo, Yitong Yin +1
We give new algorithms based on Markov chains to sample and approximately count satisfying assignments to -uniform CNF formulas where each variable appears at most times. Fo…
cs.DS2012★ 4 cited
Approximate Counting via Correlation Decay on Planar Graphs
Yitong Yin, Chihao Zhang
We show for a broad class of counting problems, correlation decay (strong spatial mixing) implies FPTAS on planar graphs. The framework for the counting problems considered by us i…