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

　　邓小铁老师的报告题目是“PPA Complete Problems”。报告一开始邓老师首先提出了这样一个问题，已知图G，其顶点集V={1,2,…,},任意顶点的度数都不超过2，且已知顶点{1}满足d(1)=1，问如何找到该图中其他度数为1的顶点。该问题看似不难，一个直观的方法是follow {1} till the end of line，但是由于图G中的顶点有个，使用该方法需要花费指数时间。如果一个函数计算问题能够通过多项式时间变换的方法转变为这样一个图的搜索问题，那么该问题就属于PPA Problems。有向图上的情况被称为PPAD Problems。

　　接着，邓老师详细介绍了与之相关的几个问题，包括Sperner's lemma、SMITH Problem（在一个3-正则图上寻找第二条哈密顿回路）、Nash Equilibrium、Cake Cutting等。

　　最后，邓老师介绍了该问题的发展历程与研究现状。在今年的STOC会议收录的论文中，证明了Consensus Halving Is PPA-Complete。

报告人简介：

　　邓小铁，1982年于清华大学获得学士学位，1984年于中国科学院获得硕士学位，1989年于斯坦福大学获得博士学位。1984-1985年，任中国科学院系统科学研究所助理研究员；1991-1999年任加拿大约克大学计算机科学与工程系助理教授、副教授；1997-2012年任香港城市大学计算机科学与工程系副教授、教授、讲席教授，同时，于2010年-2012年兼任英国利物浦大学计算机科学与工程系讲席教授；2012-2017年任上海交通大学计算机科学与工程系讲席教授；2017年12月入职北京大学，任信息科学技术学院前沿计算研究中心讲席教授。

　　邓小铁教授的主要科研方向为算法及博弈论、互联网经济、在线算法，及并行计算。2008年，他因在博弈论算法的贡献获选ACM Fellow。邓小铁教授近期的研究兴趣包括算法博弈论研究、均衡和机制设计、互联网广告系统、云计算定价及资源分配、社交网络行为分析及推荐系统，以及交通及物流网络算法。作为项目负责人，他曾承担十几项加拿大、香港、英国，及国家基金委科研项目，并担任多种国际期刊编委。他曾担任多个国际学术会议主席，并发起网络经济学国际三大洲（亚洲欧洲美洲）循环举办的全球性会议互联网及网络经济学术会议The Conference on Web and Internet Economics (WINE)。他在算法博弈论方面及网络搜索的研究成果，被国际同行广泛引用，发表论文200余篇，被引用数千次；多次做国际学术会议特邀报告；曾获得IEEE理论计算机学术会议FOCS的最佳论文奖；其成果“关于图与组合优化的若⼲经典问题的研究”获2015年度⾼等学校科学研究优秀成果奖 （⾃然科学）二等奖（排名第⼆）。应用方面获得多项美国专利及国家专利，曾担任主要互联网公司机制设计顾问。