近日，我院2020级本科生杨熊鑫与美国斯坦福大学博士后刘天宇，共同撰写的论文“Beyond windability: Approximability of the four-vertex model”被理论计算机科学领域国际期刊Theor. Comput. Sci.（CCF B类期刊）接收。杨熊鑫就读于我院计算机科学与技术专业，自2021年开始在付治国教授的指导下从事科研工作。

期刊简介：《理论计算机科学》（Theoretical Computer Science，简称为Theor. Comput. Sci.）创刊于1975年，是理论计算机科学中最主要的学术期刊之一。Theor. Comput. Sci.是CCF与清华大学计算机学科群推荐B类期刊。

期刊名称：Theoretical Computer Science

期刊类别：中国计算机学会推荐B类期刊

论文题目：Beyond windability: Approximability of the four-vertex model

作者顺序：刘天宇，杨熊鑫（根据理论计算机科学惯例，论文作者按姓氏字母序排序）

通讯作者：杨熊鑫

论文概述：在本文中，我们研究了四顶点模型的可近似性。四顶点模型是六顶点模型的一个特例。我们证明了，尽管近似计算四顶点模型的配分函数在最坏情况下是NP-难的，但当其输入满足某个布尔域上的线性方程组时，可以为其设计一个完全多项式时间随机近似方案。 该完全多项式时间随机近似方案由一种被称为蠕动过程的马尔可夫链给出，其状态空间和快速混合性依赖于线性方程组的解。为了突破为六顶点模型设计随机近似算法时可缠绕性的障碍，我们引入了一种新的规约技巧——环分解。此外，我们还探索了该技术在平面图及相关图上的应用，提供了对应四顶点模型的高效采样算法。

论文链接：https://doi.org/10.1016/j.tcs.2024.114491