2018年7月9日-13日，由北京大学前沿计算研究中心承办的“计算理论周”系列讲座在北京大学静园五院举行。“理论周”由中心邓小铁老师发起及组织，邀请计算机理论方面的多位知名专家学者，介绍计算机理论方向的前沿课题，并就相关问题和同学们开展深入讨论。

　　王捍贫教授的报告题目是“Approximability of the Six-vertex Model”。对于一个四正则的欧拉图，每个节点都对应着六种形态，我们给每种形态赋予一种权值，其中对称的两种形态拥有相同的权值，我们在图上对这些权值的乘积做一个求和，结果对应着物理中的一个子系配分函数。精确计算这个结果是NP-hard，目前已知最好的近似算法解决了部分情况下的问题，而且证明了一些情况是无法近似的。但是目前依旧有一些情况我们并不清楚是否可以近似，或者尚未给出近似算法。这个问题也是该领域比较重要的一个Open Problem。

报告人简介：

　　王捍贫，男，博士，教授，博士生导师，北京大学软件所副所长、中国人工智能学会离散数学专业委员会副主任委员、《软件学报》责任编委。研究方向为软件理论、计算逻辑、算法分析和计算复杂性，主持973子项课题、863项目课题、国家自然科学基金等7项。2011年获教育部高等学校科学技术奖励自然科学一等奖1项。