——记南京大学计算机学院教授栗师

李 莉  谭 凯　　

　　

　　2004年9月，图灵奖获得者姚期智教授辞去在普林斯顿大学的终身教职，正式加盟清华大学高等研究中心，成为清华大学引进的又一位世界级大师。姚期智的全职回国，填补了国内计算机学科的一项空白。这不只是因为他无可争议的学术大师身份，更因为在他所从事的算法和复杂性领域，当时几乎看不到中国本土学者的身影。

　　姚期智带来了一个由国际算法和复杂性领域最出色的华人学者组成的讲习教授组，并亲自讲授“理论计算机科学”课程，首开国内计算机理论教育先河。这不仅显著改变了国内理论计算机领域的研究面貌和学术水平，也在广大华人学生、学者中产生了潜移默化的影响。

　　作为第一届清华学堂计算机科学实验班（由姚期智创建，以下简称“姚班”）毕业生，栗师对理论计算机科学的兴趣就在彼时被点燃。此后追寻着兴趣指引的那束光，栗师远渡重洋在普林斯顿大学、芝加哥丰田技术研究院、纽约州立大学布法罗分校求学、工作多年。在理论计算机科学与算法设计领域深耕，他在若干经典和基础问题研究上实现了重大突破，解决了诸多领域内长久悬而未解的难题。

　　鹏程万里，回归家国。2023年年初，已是纽约州立大学布法罗分校副教授的栗师毅然辞去国外教职，入职南京大学。怀抱“为中国的理论计算机教育事业添砖加瓦”的坚定信念，栗师以在“六朝古都”的事业开展为起点，开启了他笃行不怠的新征程。

姚班岁月 仰望“高山”

　　与诸多清华姚班学生一样，栗师与清华结缘，亦始于计算机竞赛。从高中开始，他接连获得全国信息学奥林匹克竞赛金牌，并由此入选国家队，在2024年希腊雅典举行的第16届国际信息学奥林匹克竞赛中，他为中国斩获国际金牌。

　　保送清华后，栗师对计算机的兴趣有增无减，因环境氛围浸染，他更是在有意识地寻找自己的方向。栗师对理论分析、算法设计的兴趣早在高中参加竞赛时就已萌芽。一些题目需要先通过理论分析证明算法的正确性，才能进一步设计程序去解答，这让栗师认识到算法分析和设计是编写程序的第一步。而姚期智全职回国在清华创办姚班，开设“理论计算机科学”课程，为栗师夯实理论基础提供了难得的机缘。

　　作为姚班的第一届毕业生，虽已离开清华园近二十年，但忆及在姚班求知的课堂点滴，栗师仍历历在目。“从清华到王府井怎么走路程最短？男女生如何选择约会对象成功率最高？教学楼里的自动售货机如何付款最划算？这些贴近实际生活的例子，大大激发了学生的兴趣和求知欲，更重要的是让我们体会到基本数学工具的强大威力，明白理论从何处来，可向何处去。”栗师介绍，每次上课，姚期智都会精心选择生动典型的实例，将学生引入最根本的理论问题中。

　　在姚班的课堂上，似乎感觉不到老师和学生的分别。全英文交流，没有台上台下、课上课下的分明界限。学生们用流利的英语提问，问题尖锐而幽默，课堂上不时响起阵阵笑声。这样的课堂，让人很难想象，讲授的内容是艰深难懂的理论计算机科学。在开放包容的课堂环境影响下，学生们变得活跃而自信。

　　轻松的课堂并不代表姚期智放松了对学生的要求，恰恰相反，他的课是出了名的容量大、习题多。所有作业必须以英文完成，而且要用专门的科学论文排版软件来写。对于老师的苦心，同学们大多能够理解。在清华大学对本科课程进行的学生问卷评估中，“理论计算机科学”课程在所有理论课中排名靠前。

　　为与产业界接轨、与国际接轨，姚期智更将微软的研究员、国外顶尖大学的教授请进了课堂。他与微软亚洲研究院沈向洋院长一起探讨、编写了教学计划，有多门核心课程由微软亚洲研究院的高层研究人员讲授。这些研究人员活跃在计算机研究和开发领域的最前沿，他们将最新的科研进展和课题引进教学，内容丰富、信息量大、难度高。

　　国际知名学者亦在课堂上深入浅出地介绍他们各自专长的研究领域。美国两院院士、1985年“图灵奖”得主理查德·卡普（Richard Karp），2002年“图灵奖”得主之一、著名密码学家阿迪·萨莫尔（Adi Shamir）……这些名字都曾出现在讲学名单上。

　　与此同时，姚期智还致力于将最优秀的学生送到国际顶尖大学学习、交流。在他的推荐下，栗师有机会进入普林斯顿大学继续深造，并在那里确定了自己未来的研究方向。在大师的课堂里，在世界一流学者和高级研究人员的指导下，接受最先进的计算机理论教育和工程教育，作为姚班的一员，栗师感到自己是幸运的，他从不掩饰对于清华姚班经历的感激。

　　在清华和姚班，栗师见到了“高山”。以此为起点，仰望高山、攀登高山、成为高山，栗师在理论计算机科学探索的路途上一直步履不停。

异国“三部曲” 遇良师交良友

　　计算机技术日新月异，对社会生活产生了深远影响，理论计算机科学作为其基石，具有不可忽视的重要性。理论计算通过抽象、建模和算法设计等方法，能够解决各种现实世界中的问题。例如优化算法可以帮助制订最佳路径规划，从而提高交通效率；图像处理算法可以改善医学影像质量，提升医疗诊断水平。理论计算为各行各业提供了工具和方法，使得解决复杂问题变得更加高效、准确。

　　通过分析设计算法，成功解决难以突破的问题，为栗师带来了喜悦，这也是吸引他愿意在相关方向继续深造并持续探索的关键因素。

　　普林斯顿大学在理论计算机科学领域享有极高的声誉，以卓越的师资力量和研究成为众多研究者心中的圣地。它记录了博弈论大师约翰·纳什（John Nash）波澜壮阔的人生经历。20世纪最伟大的科学家爱因斯坦（Albert Einstein）曾在这里度过了生命中最后的22年时光，并发出这样的感叹：“我舒服得像一头冬眠的熊，在颠沛的一生里，从未试过如此像在家里一样的地方。”漫步在普林斯顿大学爬满常春藤的哥特式校园内，无人不被其优美景致所吸引。因远离喧嚣，这里成为众多学术精英冥想玄思、探寻真理的绝佳场所。

　　栗师享受普林斯顿大学的宁静和谐，与来自世界各地的优秀学子共同学习和成长，他更感受到知识的力量和创新的魅力。学校学术氛围浓厚，一流的教授和研究人员，在各自的领域具有世界级的影响力。在这里，栗师听到了各种前沿的学术讲座；与顶尖学者进行深入交流，激发了他对知识的渴望和对学术的热情；图书馆资源丰富，为栗师提供了强大的学术支持，他沉浸在书海中，探索知识的边界，满足自己的求知欲。

　　普林斯顿大学的教授治学态度非常严谨。导师摩西·查理卡教授（Moses Charikar）不仅关注栗师的学术成绩，更关心他的个人成长。导师会耐心地解答栗师提出的问题，并鼓励他提出自己的观点，培养他独立思考和解决问题的能力，这种严谨的教学态度让栗师在学习过程中不断进步。导师还会经常提出一些新颖的想法，让学生去讨论，在不同观点的碰撞中，栗师收获很大。

　　在普林斯顿大学的求学，让栗师的知识积累更完善、视野更开阔，在兴趣牵引下做探索的同时，他也在确定着自己的研究方向，并最终将方向聚焦到理论计算机科学的子领域——近似算法和组合优化理论。

　　在博士求学期间，栗师独立解决了理论计算的经典难题设施选址问题。相关成果发表于欧洲理论计算机科学学会（EATCS）旗舰会议，并获得最佳学生论文奖，论文的期刊版发表于理论计算机科学顶级期刊《信息与计算机》（Information and Computation）。时至今日，这一结果仍是设施选址这一经典组合优化问题的最先进算法之一。

　　在普林斯顿大学的求学是栗师生命中的一段美好经历。在这里他遇良师、交良友，个人能力获得了极大提升。虽身处异国他乡，因有新老朋友在身边，他未有过作为异乡人孤立无援的感觉。“鬲融、黄志毅这些姚班的老同学都在美国，大家经常联系，周末常常一起打牌，买菜做饭，春节一起包饺子。有时在学术会议上遇到，或者出差在同一个地方，大家也会聚在一起聊近况，聊在清华读书时同学们间的趣事，也会讨论学术问题。”栗师说。

　　从普林斯顿大学毕业后，栗师进入芝加哥丰田技术研究院担任助理研究教授，开始进行独立的科学研究。虽已是一名独立的研究者，但他一直与一些知名学者保持着密切的合作。丰田技术研究院朱莉娅·秋思豪教授（Julia Chuzhoy）做事专注认真，能融会贯通各种知识、思想，做出自己的创新成果，这让栗师受益匪浅。马里兰大学的阿拉温德·斯里尼瓦斯（Aravind Srinivasan）教授对科学热情洋溢，受邀去他家里，栗师常常与他展开热烈又极富启发的讨论。洛桑联邦理工学院的奥拉·史云逊教授（Ola Svensson）风趣幽默，能用浅显易懂又极为形象的表达，让栗师对某些问题豁然开朗。

　　通过与这些学者合作，栗师拓展着自己认知的边界，对做怎样的科研题目有了更加清晰的认识，并运用之前的积累主动做选择。对网络路由问题、聚类问题，他都做了一些探索，并收获了非常有价值的成果。

　　栗师在美国的经历分为3个阶段，在普林斯顿大学他实现了知识的迅速积累，在芝加哥丰田技术研究院他走上了独立探索之路，而在纽约州立大学布法罗分校的任教经历，则让他由关注自己向关注学生转变，这为他带来了独特的体验。

　　“作为老师，我有很大一部分精力花在如何教好学生上，这与之前做研究很不一样。不仅要自己做好研究，还要带领学生做好研究，为学生选择适合他们的课题，激发他们的兴趣，将自己学到的知识、经验、教训，系统性地传达给学生，让他们少走弯路。如何将自己掌握的知识更有效率地传授给学生，需要做很多功课。”栗师说。

　　为了教好学生，栗师花了很多精力，但他喜欢教师这一角色，他愿意将自己所知与学生分享，在学生对知识热切渴求的目光中，他更确定了自己应该在什么样的位置和角色上发挥作用。这也是栗师回国选择到南京大学任教的一个重要原因，为国内理论计算机教育事业的发展壮大尽一份力，栗师做好了准备，并有信心去做好这件事。

解锁思维密钥 攻克经典难题

　　在美国求学工作期间，专注于科研，致力于创新，栗师在近似算法以及相关领域的多个基础问题上都收获了突破性的研究成果。

　　栗师解决了网络路由理论中的一个经典难题——带拥塞边独立路径问题；对设施选址问题给出了迄今最好的近似算法，且已保持这一纪录10年；对聚类和调度问题分别发展了创新的理论工具，并给出多个当前最好的近似算法。这些成果获得国际同行专家的高度评价，被描述为“突破”“突出”“最佳”等共达数十次。栗师因此获得纽约州立大学布法罗分校杰出学者奖，以及美国国家科学基金成就奖。

　　栗师介绍，网络路由问题是一类基本的图上组合优化问题。其中，一个经典难题是如何在网络拥塞受限的前提下，将尽量多的单位货物从出发点送到目的地。与朱莉娅·秋思豪合作，他们给出了一个在优化近似比和网络拥塞度这两方面同时达到理论最优的高效算法，解决了这一网络路由方面的经典理论难题。

　　除路径优化外，栗师对另一类经典的网络路由问题——斯坦纳树问题，也进行了探索，并给出了一个近似比达到理论最优的拟多项式时间算法，被许多专家称为在这一问题上“对于拟多项式时间算法最好的可能”。成果被美国密歇根大学维斯瓦纳特·纳加拉简..（Viswanath Nagarajan）教授等人在论文中引用10次以上，并利用算法发展的技术解决了多个相关问题。

　　栗师不仅为经典的网络路由问题给出了最优解，在设施选址问题上也给出了最优解。设施选址问题是近似算法、运筹学和组合优化领域一个教科书级别的问题，对它的解决涉及多种近似算法设计思想和组合优化技术。在美国高级优化算法课程经典教科书《近似算法设计》一书中，共有5个章节介绍解决这个问题的不同算法，由此足见此问题在近似算法领域的核心地位。同时，对这一问题的研究对于近似计算复杂性理论的完善也有重要意义。

　　人们已知，在特定计算复杂性假设下，相关问题的任何多项式时间近似算法都不可能达到比1.463更小的近似比。栗师在2011年读博士时针对设施选址这一经典组合优化问题给出了一个近似比达到1.488的高效近似算法，这已非常接近1.463这一理论最优的近似比下界。另外，除了最经典的无容量限制版本的设施选址问题之外，栗师也研究了具有下界约束的设施选址问题，并给出了首个达到常数近似比的多项式时间近似算法，成果作为单独作者论文发表于算法理论顶级会议上。

　　聚类是与设施选址问题具有内在联系的一类组合优化问题。k中值是一种典型的聚类问题，对于非监督机器学习有重要的意义，同时也在近似算法和组合优化领域占据核心地位。关于k中值问题，长久以来的一个障碍是其高效近似算法的近似比无法突破3这一界限，这是由于此前所有已知算法都无法克服此问题特有的一个根深蒂固的技术障碍。

　　栗师给出了一个新的k中值近似算法，首次将近似比从3降到1+√3，突破了自2001年以来k中值问题长达十余年的技术瓶颈。成果发表于计算机顶级会议（2013年计算理论年会，STOC’13），并作为会议的优秀成果之一被邀请至理论计算机科学顶级期刊《美国工业与应用数学学会计算杂志》（SICOMP）发表。美国计算机协会（ACM）会士、戴克斯特拉（Dijkstra）奖得主、马里兰大学阿拉温德·斯里尼瓦斯（Aravind Srinivasan）教授在他的论文中多次称这一结果为“突破”，优化领域哈奇扬（Khachiyan）奖得主、柏林洪堡大学沃纳·罗密施（Werner R.misch）教授称这一新算法为“创新性的近似算法”。

　　此外，栗师也研究了包括容量受限、容错和在线一致性等需求在内的k中值问题，系列成果发表于计算机国际顶级会议上。在此基础上，他发展出一套迭代舍入算法框架，系统化地解决多种聚类问题，包括著名的存在离群点的k均值聚类问题，并给出这一问题首个常数近似比的高效近似算法。成果发表于计算机顶级会议（2018年计算理论年会，STOC’18）。加拿大阿尔伯塔大学穆罕默德·萨拉瓦提普尔（.Mohammad Salavatipour）教授在论文中指出这一成果是此类重要聚类问题的“首个真正常数近似”。

　　鉴于最优化调度理论在近似算法、在线算法、运筹和组合优化领域都有着重要的地位和悠久的历史，栗师对此领域里的若干经典问题也提供了新的研究视角和近似算法。他提出了一种包含时间标记变量的线性规划框架，可系统化地对不同调度问题设计近似算法，让多个调度问题获得迄今为止较先进的结果，成果作为单独作者论文发表于理论计算机科学顶级会议（2017年计算机科学基础研讨会，FOCS’17）上，并作为会议的优秀成果之一被邀请至理论计算机科学顶级期刊（SICOMP）发表。此后，栗师在计算机国际顶会上发表的一系论文中，又继续提出了不同的技术来解决不同种类的调度问题。

　　敢于挑战经典难题，并收获诸多极为重要的成果，栗师坦言在此过程中没有特别的经验可以分享，只有坚持、不放弃。“有些问题会让你无从下手，这常令人感到沮丧。虽然会走很多弯路，但柳暗花明的那一瞬间会让人无比振奋，觉得坚持是值得的。”栗师说。

　　一路攻克难关，栗师对出现的瓶颈有了一套自己的应对方法，先放一放，做其他课题，稍微变换一下目标，大多时候之前的难题也会随之而解。“其实做理论方向研究，项目与项目的边界没有那么明显，在一个大背景下有很多应用，比如在网络路由问题中也有一些调度问题，包括人工智能训练模型时，也要遇到聚类问题，某一问题的解可以解决很多其他的问题。”栗师介绍。

　　遇到难题时，栗师也会跟其他学者讨论，借鉴他们的经验。不同的人背景不同，所了解的知识也不同，往往能带给他一些醍醐灌顶的启发。另外，做理论计算机科学研究，需要用到线性代数、概率论、组合数学等数学工具，有扎实的数学基础，能找到问题的关键点，这都是难题得以突破的一些条件。

　　对于栗师来说，能在理论计算机科学研究这条路上走下来最关键的动力，还是他在做此项工作中能获得极大的乐趣。“现实中大量的组合优化问题，完成精确计算是不现实的，因此对于这些优化问题的有理论保障的高效解决，需要诉诸计算效率（时间复杂）和优化性能（近似比）两方面都有严格理论保证的近似算法。所以，我做的事情是在提升算法速度的前提下，如何把解做得更好，不一定要达到最优，但是越优越好。就是在效率和解的优劣之间找到一个平衡，用简单的描述，得到一些通用的技术，这些技术可以用到很多问题的解决上，这件事本身是很美妙的，也是我做算法研究的意义所在。”栗师坦言。

鹏程万里 回归家国

　　2024年4月27日，“秩年对话”校友论坛于清华如期举办。毕业多年的校友欢聚一堂，共忆青葱岁月。栗师也在会上分享了学术发展、职业规划等方面的心路历程。

　　在场聆听的同学表示：“许多片段引起了我们强烈的共鸣。当栗师学长说到‘我相信我还可以为中国的理论计算机教育添砖加瓦，于是坚定回国’的时候，我仿佛看到了20年前归国的姚期智先生，也立刻想起了之前姚先生对我们的寄语‘鹏程万里，回归家国’。”

　　“姚教授全职归来，并以其人格魅力带动一批人才回国发展计算机学科，堪称是一面‘旗帜’，产生一个‘放大效应’，不仅显著改变了国内理论计算机领域的研究面貌和学术水平，也在广大华人学生、学者中产生了潜移默化的影响。”栗师说。“鹏程万里，回归家国”，虽在海外打拼，但他一直心系祖国，希望学成回国效力，不负清华的培养，不负自己的年华。

　　在与南京大学尹一通教授的交往中，栗师了解到南京大学计算机学科的悠久历史和办学质量。半个多世纪以来，几代南京大学计算机人秉承优良传统，不断开拓创新，在学科建设、人才培养、科学研究、国际交流等方面都取得了显著的成就。进入新世纪以来，在新一代学术带头人和系党政领导班子的带领下，南京大学的计算机学科建设进入快速发展期。

　　尹一通本科毕业于南京大学计算机科学与技术系，2009年博士毕业于耶鲁大学计算机科学系，同年回到母校南京大学任教，并担任南京大学理论计算机科学研究组的团队负责人。负责引才的他，曾多次找到栗师。在此机缘下，栗师将南京大学作为了回国筑梦的起点。

　　南京大学及其计算机学院为归国人员提供的配套支持助力栗师的工作顺利开展。尹一通及理论团队所有成员的鼎力相助让栗师很自然地完成了思维和习惯上的转换，适应了国内环境。

　　“实验科学需要买很多设备，如果换了工作环境，一切都要从头开始，但理论研究不同，一台电脑、一台打印机，有笔和纸就足以开展工作。有便利的通信条件，之前在美国跟别人的合作，回国后还可以继续，因为工作不会受到很多外在条件的限制，所以工作环境的变化对我的影响倒不是很大。”栗师坦言。

　　入职伊始，栗师就在着手组建团队，被录取的4个大三学生虽在下学期才正式加入团队，但他们已在跟随栗师做毕业设计，并都已完成了一篇优质论文。“做理论研究，其实团队的概念没有那么明显，不是所有学生都要集中精力来解决一个大问题，所以我带学生的方式是让他们自由发挥，他们可以一起做一个问题，也可以单独做自己想做的问题，还可以自由地选择合作者，与南京大学的其他老师，甚至其他学校的学生和老师合作。”栗师说。

　　除鼓励学生进行自由探索外，栗师希望学生对科研真正有兴趣。“如果没有发自内心的热爱，其实很难说服学生，让他们留在这个领域持续做下去。兴趣是工作的动力，否则会变成一种负担。”他鼓励学生沉下心、专注做高质量的科研，勇于挑战有难度的问题。同时，这也是他对自己的要求。

　　回国前，栗师已对未来的工作做了规划，一如既往向难题发起挑战，他在其中一个新课题中关注了与经济学相关的问题。“效益最大化和保证公平性是商品分配的两个目标。二者如何达到平衡，是算法研究里的一个公开难题，但我们发现其实用一个很简单的方法就可以解决，目前论文已发表并且获得优秀论文奖。这是与学生一起做的一个新工作，后续工作还在继续。”栗师介绍。

　　与国家人工智能的重大发展战略相结合，栗师也在布局自己的研究。他坦言，人工智能的发展给一些领域带来的冲击大到无法想象，而理论研究相对来说受到的影响要小一些。在保持理论研究独立性的同时，如何与人工智能结合，用理论来解释人工智能的一些内在机制，成为栗师想要探索的课题。

　　“因为有在组合优化算法设计上的扎实基础，我相信向这一方向拓展会较容易。而且随着团队壮大，每个人关注的问题不一样，这就要求我的兴趣也必须广泛一点，这样才能与学生做更好的交流。”在关注传统核心问题的同时，栗师也希望拓宽自己的研究领域。

　　栗师赞同爱因斯坦所说：不能满足于找一块最薄的木板来钻孔，并且钻上许许多多的孔，搞科研应勇于钻厚木板。“我一路的经历都是在钻厚木板，未来也是如此，希望能用新视角、新思路、新解法，做更多前人没有做过的工作。”栗师说。

专家简介　　

　　栗师，南京大学教授、博士生导师。本科毕业于清华大学计算机科学与技术系，以及第一届姚期智理论计算机科学实验班。于普林斯顿大学获得博士学位，之后在芝加哥丰田技术研究院担任助理研究教授，在纽约州立大学布法罗分校担任助理教授，并于2020年在该校获得副教授职称。2023年初入职南京大学。栗师的研究方向为理论计算机科学领域与算法设计。他在若干经典和基础问题上做出重大突破，解决了很多多年未解的公开难题。多个结果分别获得理论计算机科学顶会（ICALP 2011）单独作者最佳学生论文奖、领域顶级会议2012年计算机科学基础研究会（FOCS 2012）最佳论文奖、ICALP 2024最佳论文奖。多项结果发表于计算机科学领域的旗舰期刊《美国计算机协会期刊》（Journal of the ACM，JACM），理论计算机科学最高期刊《SIAM·计算》（SIAM Journal on Computing，SICOMP）以及《信息与计算》（Information and Computation，I&C）等国际一流期刊上。他在FOCS、STOC和SODA三大领域顶级会议上发表文章近30篇。