Page 144 - 《软件学报》2025年第10期

刘莹 等: 正则图上对称双态自旋系统相关的细密度二分定理 4541

[29] Liu Y, Chen S. Sub-exponential time lower bounds for #VC and #matching on 3-regular graphs. In: Proc. of the 41st Int’l Symp. on
Theoretical Aspects of Computer Science (STACS 2024). Clermont-Ferrand: STACS, 2024. 49: 1–49: 18. [doi: 10.4230/LIPIcs.STACS.
2024.49]
[30] Chen HB, Curticapean R, Dell H. The exponential-time complexity of counting (quantum) graph homomorphisms. In: Proc. of the 45th
Int’l Workshop on Graph-theoretic Concepts in Computer Science. Vall de Núria: Springer, 2019. 364–378. [doi: 10.1007/978-3-030-
30786-8_28]
[31] Valiant LG. Holographic algorithms. SIAM Journal on Computing, 2008, 37(5): 1565–1594. [doi: 10.1137/070682575]
[32] Cai JY, Lu PY, Xia MJ. Holographic algorithms by Fibonacci gates and holographic reductions for hardness. In: Proc. of the 49th Annual
IEEE Symp. on Foundations of Computer Science. Philadelphia: IEEE, 2008. 644–653. [doi: 10.1109/FOCS.2008.34]
[33] Guo H, Huang SX, Lu PY, Xia MJ. The complexity of weighted Boolean #CSP modulo k. In: Proc. of the 28th Int’l Symp. on Theoretical
Aspects of Computer Science (STACS 2011). Dortmund: STACS, 2011. 249–260. [doi: 10.4230/LIPIcs.STACS.2011.249]

附中文参考文献:
[9] 邱国良, 张驰豪. 铁磁性双态自旋系统配分函数的可近似性. 计算机科学, 2020, 47(5): 22–26. [doi: 10.11896/jsjkx.200200119]
[10] 白宗磊, 王捍贫, 曹永知, 王璐璐. 树上自旋系统的快速采样算法. 计算机学报, 2022, 45(10): 2093–2116. [doi: 10.11897/SP.J.
1016.2022.02093]

刘莹(1996－), 女, 博士生, CCF 学生会员, 主要
研究领域为理论计算机科学, 计数复杂性.