12月15日上午,东北师范大学付治国教授应邀参加37000cm威尼斯第四届研究生学术文化节,为师生线上作题为《平面图上计数问题的计算复杂性分类》的学术报告,37000cm威尼斯芦碧波主任主持报告会,部分教师和研究生参加了报告会。
付治国教授为东北师范大学信息科学与技术学院副院长、博士生导师,长期研究全息算法理论、计数问题的计算复杂性分类、深度学习的泛化误差分析等计算机领域相关问题,相关成果发表在STOC、FOCS、SODA、SIAM J. Computing、AAAI等计算机领域的顶级期刊和会议。
报告会上,付治国教授首先介绍了平面图上计数问题的计算复杂性分类问题定义,详细介绍了近年来取得的一系列进展。然后,分析了平面图上计数问题计算复杂性分类问题的求解策略。最后,介绍了以计数图同态、计数约束满足问题、Holant问题为经典框架的平面图上计数问题计算复杂性分类的主要方法,并梳理了该方法与全息算法的关系。
此次报告会的成功举办,有效深化了广大师生对计算机理论中计数问题计算复杂性分类的认识与了解,拓展了学生的研究思路,为他们跟踪掌握学科发展动态及后期研究提供了良好思路。