2 papers
cs.DS2019
Counting independent sets and colorings on random regular bipartite graphs
Chao Liao, Jiabao Lin, Pinyan Lu +1
We give a fully polynomial-time approximation scheme (FPTAS) to count the number of independent sets on almost every -regular bipartite graph if . In the weighted case,…
cs.DS2018
Zeros of Holant problems: locations and algorithms
Heng Guo, Chao Liao, Pinyan Lu +1
We present fully polynomial-time (deterministic or randomised) approximation schemes for Holant problems, defined by a non-negative constraint function satisfying a generalised sec…