10月19日下午，应我校软件学院邀请，东北师范大学博士生导师付治国教授应邀为我校计算机应用技术重点学科在线上作了一场题为“平面图上计数问题的计算复杂性分类”的学术报告。软件学院及相关院系师生共100余人参加了此次报告会。
计数问题研究是理论计算机和组合优化理论中的一个热点问题，该问题也是人工智能和计算机科学领域的经典问题，这个领域的极值问题在图论中很有吸引力。付治国教授深入浅出的对图的计数问题进行了系统讲解，首先从子树计数的背景和三个框架讲起，随后讲解了布尔域上计数约束满足问题的计算复杂性三分定理；布尔域上对称约束下Holant问题计算复杂性分类定理；以及六顶点模型的计算复杂性分类定理。此外付教授还分享了瓦利安特（Valiant）的全息算法（holographic algorithm）的巧妙构造，以及完美匹配(Perfect matching)算法研究的最新进展。
整场报告内容丰富有趣，引人入胜，充分体现了计算之美，大大地激发了教师和同学们对图的计数问题研究的了解。报告中付治国教授对东北师范大学计算机和人工智能研究生招生政策进行了讲解，还与我校的师生进行了互动交流，如何进行理论以及应用基础研究给出了很好的建议，同时对我校图计算和大数据技术团队科研和学科进行了建设性的指导。
付治国，博士、教授，东北师范大学信息科学与技术学院副院长，2009年博士毕业于吉林大学数学学院计算数学专业，2011-2012，2014-2017两度在美国威斯康星大学麦迪逊分校与哥德尔奖得主蔡进一教授合作开展研究。主要研究方向为全息算法理论、计数问题的计算复杂性分类、深度学习的泛化误差分析。相关成果发表在STOC，FOCS，SODA，SIAM J COMPUT，Information and Computation, AAAI等计算机领域的顶级期刊和会议。
