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

　　陆品燕老师的报告题目为“Roots of Polynomial and Approximate Counting”，其主题所关注的近似计数这一话题。对于许多计数问题，其难度远远高于对应的判定问题的难度；而对于有些高难度的判定问题，它对应的计数问题甚至有可能是无法完全近似的。

　　为了介绍一些近似计数的方法，陆老师从独立集的计数问题开始入手，将带条件的独立集计数问题转换成概率分布的求解问题，通过列出转移方程与Computation Tree进行递归计算。然而，Computation Tree的深度是线性级别的，因此整棵树的节点量是指数级别的。为了解决递归计算量过大的问题，可以采用Correlation Decay的方法，选取合适的深度，在计数精度和运算时间之间做权衡，达到近似计数。

　　陆老师还介绍了类似于点染色计数、匹配计数、单调合取范式可满足性计数与二分图上的点独立集计数（#BIS）问题。特别地，当限制图中的最大点度数为6的时候，#6BIS的难度和#BIS是一样的。人们猜想，#BIS的复杂性介于#SAT和FPRAS之间（如果多项式谱系不坍塌）。

报告人简介：

　　陆品燕，上海财经大学信息学院教授，副院长，理论计算机科学研究中心主任。2009年1月于清华大学计算机系获博士学位后加入微软亚洲研究院，历任理论组副研究员，研究员，主管研究员。2015年12月全职加盟上海财经大学，领衔组建理论计算机科学研究中心，经过两年时间的建设，他的研究中心在CSRankings上算法与复杂性、计算经济学两个方向已经排到亚洲第一名、世界第十五名。他的主要研究方向是理论计算机，并注重与其它学科的交叉，包括自然科学中的统计物理以及社会科学中的经济学与社会选择理论等。有60余篇科研论文在STOC、FOCS、 SODA、EC等顶级计算机理论及博弈论的国际会议和杂志发表，荣获ICALP2007、FAW2010、ISAAC2010 等重要国际会议最佳论文奖。2010年曾受丘成桐先生邀请在第五届国际华人数学家大会 (ICCM) 上作45分钟的大会报告。担任FAW-AAIM 2012、WINE 2017、FAW 2018等国际会议程序委员会联合主席，以及多次担任STOC，FOCS，ICALP等顶级国际会议的程序委员会委员。曾荣获上海市拔尖青年（2017）、中国计算机学会青年科学家（2014）、微软金星员工奖（2010）、 微软学者（2008）、清华大学特等奖学金（2007）等荣誉。