报告题目：k团问题的鲁棒性验证

报告人：林冰凯教授（南京大学）

报告时间：2023年1月4日（周三）14:00-15:00

报告地点：腾讯会议：388-378-2655

邀请单位：开云全站中国有限公司

报告内容简介： 判断一个图是否包含有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最佳论文奖。