南京大学计算机系教授林冰凯：把握理论发展新趋势 促进计算机学科进步

　　作为20世纪最先进的科技发明之一，计算机已引发深刻的社会变革，成为社会生活中不可或缺的组成部分。围绕计算机形成了研究计算机及其周围各种现象和规律的科学。其中，理论计算机科学因其涉及大量数学内容，有助于学习者深刻而直观地理解问题的本质，广受推崇。南京大学计算机系教授林冰凯选择“现代计算复杂性理论中的参数复杂性及精细复杂性”作为具体的研究领域，围绕现代计算复杂性理论，对近似计算的复杂性进行更加精细的刻画与分类这一主线，始终不改初心，成为诸多理论计算机科学研究者中的佼佼者。

　　把握趋势 深入以克难

　　现代计算复杂性理论的一个发展趋势，就是对计算复杂性进行更加精细的刻画与分类：关注计算问题在特定结构及参数的输入上表现出的具体的计算复杂性，以及计算问题的精确的计算开销。从而帮助人们更精确地理解“计算问题因何而易、又因何而难”——这也是计算理论自诞生以来的宗旨。参数复杂性与精细复杂性就是在这一背景下发展出的现代计算复杂性理论。传统计算复杂性理论研究中的一个里程碑式的发现就是PCP理论（概率可检验证明）及其对理解不可近似性的作用。与之对应的，在现代计算复杂性理论研究中，也要面对重要挑战，即精细复杂性与参数复杂性版本的PCP理论。

　　林冰凯教授与他的研究领域结缘，始于就读上海交通大学ACM试点班时。在2006—2013年，他攻读了“计算机科学与技术”学士、硕士学位，不断深入了解参数复杂性理论，其硕士论文即为《K边诱导子图问题的参数复杂性》。

　　参数复杂性领域里有一个长期悬疑的公开问题——k-BICLIQUE问题。数复杂性的开创者Downey, Rod G.和 Fellows, Michael R.在他们撰写的教科书里称该问题“经过如此多年却仍未解决乃是整个领域的一大困窘”。林冰凯教授在攻读博士学位期间独自解决了这一问题，以单独作者论文将成果发表于国际算法重要会议SODA’15，并同时获得了该期会议唯一的最佳论文奖和唯一的最佳学生论文奖。该论文的期刊版本则发表在ACM旗舰期刊Journal of the ACM上。

　　而随着这一问题被化解，林冰凯教授等发现这项工作可以导致参数复杂性领域中一些长期悬疑的难题得到突破性进展。其中就包含一些原本被认为需要参数复杂性版本的PCP定理才能解决的问题，例如支配集问题与最小距离编码问题的参数版本的不可近似性。而这也成为林冰凯教授要攻克的新高地。

　　基于k-Biclique 的突破性工作中形出的新技术，林冰凯教授等合作取得了支配集问题的首个参数不可近似性证明。成果发表在理论计算机科学重要会议FOCS 2016，作为该年度FOCS发表的优秀工作之一被邀请至理论计算机科学国际一流期刊SIAM Journal on Computing，并获得录用。一经发表，广受关注。在2019年，林冰凯教授为这个支配集问题的参数不可近似找到一个新的简洁证明，该证明获得了目前最好的不可近似比。这一结果以单独作者论文发表在2019年欧洲理论计算机重要会议ICALP上，并且获得trackA论文的最佳论文奖。

　　小距离编码问题在编码理论中属于很受关注的问题。基于在k-Biclique问题取得的结果，林冰凯教授等合作证明了最小距离编码问题的参数算法不可近似性。该证明还可以推广至格上的最短向量问题的参数不可近似性。格上的最短向量问题具有相当的计算困难性，甚至还被用于公钥密码设计。该证明为基于格的加密提供更精确的复杂性基础。该合作成果已投稿至JACM，并获得审稿专家建议录用。

　　在参数近似算法的研究中最重要的课题就是探索高精度复杂性与参数复杂性框架下的PCP定理，也就是要发展出一套成熟的证明参数近似算法下界的工具。目前，世界顶尖的理论计算机领域研究者都向此课题发起挑战，但具体实现方式大相径庭。而林冰凯教授所从事的通过一些具有Threshold性质的组合构造来设计Gap-Reduction，从而证明参数近似算法下界。他还打算将经典的证明PCP定理的部分技术放到高精度复杂性的框架下进行分析，从而寻求某些突破。在研究参数近似算法下界的同时，林冰凯还将争分夺秒地从事高精度复杂性框架下的近似算法的设计。

　　培养后辈 浅出以授业

　　在日本国立情报学研究所当了3年研究员后，林冰凯教授于2019年9月正式归国，就职于南京大学。他一方面继续从事高精尖学术研究，另一方面投身到基础教育第一线——承担本科生和研究生的组合数学的教学任务。

　　面对着后辈们求知若渴的双眼，林冰凯希望自己能成就风行草偃之功，但是组合数学包含内容范围广，缺乏串联主线，让理论功底欠佳的学生有种不连贯的感觉。对林冰凯教授而言，在深入研究之后如何成功做到“浅出”，成为考验其学术功力的新战场。

　　林冰凯教授始终认为，“掉书袋”对学生而言，并没有太多实际意义，更不会为他们提供真正的学术帮助。林冰凯教授推崇著名数学家W. T. Gowers所提出“组合数学里重要的是证明定理中用到的更一般的原理，而不是定理本身”理念，更愿意用通俗易懂的内容来解释艰涩的微言大义。在覆盖基础内容的前提下，林冰凯教授还适当引入部分前沿课题。其中就包括介绍了当今图论算法领域的重要概念树分解（Tree decomposition）。虽然这一成果在国际范围内广受关注，但国内学生对其还较为陌生。林冰凯教授悉心帮助学生们打开了另一扇学术之窗。另外，林冰凯教授还会基于个人第一手科研经验进行内容创新。比如在讲授Ramsey定理时，传统的关于Ramsey定理的应用往往需要用到集合上的Ramsey定理。而集合上的Ramsey定理相比普通的Ramsey定理要抽象，对学生的理解能力是一项挑战。所以林冰凯教授就用他在ICALP 2012论文中的结果作为例子，成功让学生们理解了原本的Ramsey定理在设计图算法上的应用。

　　林冰凯教授的授课方式和内容深受广大学生欢迎。桃李不言，下自成蹊。

　　多年来，林冰凯教授始终把握理论发展新趋势，为行业发展贡献智慧和力量，促进了理论计算机科学进步；同时，为培养学术后备军，他满怀赤诚，不断传道授业解惑，一片冰心在玉壶。

关注读览天下微信， 100万篇深度好文， 等你来看……