报告题目：平面图上计数问题的计算复杂性分类

报告人：付治国

报告时间：2022年12月29日（周四）10:00-11:00

报告地点：腾讯会议：147-184-288

邀请单位：88038威尼斯

报告内容简介：

计数问题的计算复杂性分类近年来取得了一系列进展，研究者建立了一系列计算复杂性二分定理，相关成果得到了哥德尔奖、富尔克森奖等著名奖项的肯定。平面图上计数问题的计算复杂性分类目标是将计数问题分为如下3类：（1）一般图上可解；（2）一般图上#P-hard，但在平面图上可解；（3）在平面图上#P-hard。其中（2）中的问题与全息算法的关系是受到广泛关注的问题。本报告将在计数图同态、计数约束满足问题、Holant问题这三个研究计数问题的经典框架下，报告平面图上计数问题计算复杂性分类的进展，并刻画（2）中的问题与全息算法的关系。

报告人简介：

付治国，东北师范大学信息科学与技术学院教授，博士生导师。博士毕业于吉林大学数学学院计算数学专业，美国威斯康星大学麦迪逊分校博士后。研究领域为计数问题的算法与计算复杂性，成果发表在STOC，FOCS，SODA，Information and Computation等理论计算机顶级会议和期刊。