| 演讲者 | 林冰凯 | | 头衔职位 | 南京大学计算机系教授 | | 时间 | 2023年3月30日(周四)上午10:00 -11:30 | | 地点 | 江湾校区二号交叉学科楼E1006报告厅 | | 联系人 | 李元 yuan_li@fudan.edu.cn |
|  |
演讲简介
判断一个图是否包含 有k个顶点的完全子图(简称k团)是著名的NP完全问题。假设有两个人A和B。B想向A证明一个给定的图G中包含大小为k的团。最简单的做法是B把构成该团的k个顶点发送给A。然而该做法不具有鲁棒性：假设某个顶点在数据输过程中或者在A读取时发生错误，那么验证就会失败。Feige, Goldwasser, Lovász, Safra 和 Szegedy [FGLSS91]曾提出一个多项式时间算法R，对于输入图G和k，R输出一个新的图G’和自然数k’，满足：(1)当G有k团时，G’有k’团；(2)当G不含k团时，G’不包含k’/2大小的团。该算法能用来设计k团问题的鲁棒性验证：A和B使用该算法对图G进行预处理，然后B发送G’中的k’团给A，A只需验证B发过来的k’个点中有k’/2大小的团即可。[FGLSS91]算法的一个限制是k’必须很大。本报告将介绍最近对于构造满足k’是与图G’无关参数的算法R的研究成果。
关于讲者
林冰凯，本科(2010)和硕士(2013)毕业于上海交通大学ACM试点班。博士(2016)毕业于日本东京大学。2019年入职南京大学。研究领域是理论计算机科学，具体领域是计算复杂性理论中的参数复杂性(Parameterized Complexity)及精细复杂性(Fine-grained Complexity)。主要成果包括独自解决了参数复杂性领域基础性难题——k-BICLIQUE问题的参数复杂性；对经典 NP难优化问题支配集问题得到首个参数不可近似性结果；在图嵌入问题参数复杂性的二分猜想这一公开问题上取得重要进展。成果发表在Journal of the ACM (JACM)、SIAM Journal on Computing (SICOMP)、Information and Computation (IANDC) 等国际重要期刊、以及STOC、FOCS、SODA、ICALP等国际重要会议。两篇单独作者论文分别获国际算法会议SODA 2015最佳论文奖和最佳学生论文奖以及欧洲理论计算机重要会议ICALP 2019最佳论文奖。
