报告题目：Holographic Algorithm with Matchgates Is Universal for Planar #CSP Over Boolean Domain。
报告时间：2017年12月13日上午10:00-11：00
报告地点：计算机楼A521报告厅
报告人：付治国 副教授
报告人简介：
付治国，2009年在吉林大学获计算数学博士学位，现为东北师范大学信息科学与技术学院副教授，2014年-2017年在美国威斯康星大学麦迪逊分校从事计算复杂性研究。主要研究方向为计数问题的计算复杂性、包括计数问题的计算复杂性分类、全息算法以及计数问题的近似算法和随机算法，已在STOC, FOCS, SIAM. J. Computing, J.Information and Computation等著名会议和期刊发表多篇论文。
报告摘要：
We prove a complexity classification theorem that classifies all counting constraint satisfaction problems (#CSP) over Boolean variables into exactly three classes: (1) Polynomial-time solvable; (2) #P-hard for general instances, but solvable in polynomial-time over planar structures; and (3) #P-hard over planar structures. The classification applies to all finite sets of local, not necessarily symmetric, constraint functions on Boolean variables that take algebraic complex values. It is shown that Valiant's holographic algorithm with matchgates is a universal strategy for all problems in class (2).
主办单位：计算机科学与技术学院
软件学院
符号与计算教育部重点实验室
计算机科学技术研究所
