20 citations · 85 across the 30 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2021★ 1 cited
Complex contraction on trees without proof of correlation decay
Liang Li, Guangzeng Xie
We prove complex contraction for zero-free regions of counting weighted set cover problem in which an element can appear in an unbounded number of sets, thus obtaining fully polyno…
cs.DS2011★ 15 cited
Correlation Decay up to Uniqueness in Spin Systems
Liang Li, Pinyan Lu, Yitong Yin
We give a complete characterization of the two-state anti-ferromagnetic spin systems which are of strong spatial mixing on general graphs. We show that a two-state anti-ferromagnet…
cs.DS2011★ 9 cited
Approximate Counting via Correlation Decay in Spin Systems
Liang Li, Pinyan Lu, Yitong Yin
We give the first deterministic fully polynomial-time approximation scheme (FPTAS) for computing the partition function of a two-state spin system on an arbitrary graph, when the p…