国内首次！清华姚班本科生斩获全球理论计算机顶会大奖

lixiang007700

一个由3名中国本科生组成的团队，近日在全球顶会计算理论年会（STOC）上击败众多本硕博组合，摘得最佳学生论文奖。

这项结果殊为不易。其一，STOC由美国计算机协会（ACM）举办，在理论计算机科学这座山峰上，它是当之无愧的峰顶会议；其二，他们的论文从全球400多篇论文中突出重围，使其成为国内本届唯一获此殊荣的团队；其三，这是中国在校大学生首次获得该奖。

3名学生都来自清华大学“姚班”，分别是范致远、李嘉图和杨天祺。他们即将在6月23日参加STOC 2022 ，“我们正在抓紧时间准备STOC的演讲视频！”

遥遥领先同龄人的3位00后学霸，并未因此太上头，“理论计算机科学研究犹如浩瀚大海，我们所做的仅是冰山一角，是在打基础而已。将来还要付出更多的努力去解决计算复杂性领域的重要问题。”

优中择优：获奖率仅约为2.9%

理论计算机科学领域有两大顶会，一个是ACM（美国计算机学会）的STOC，另外一个是IEEE（国际电气和电子工程师协会）的FOCS。两者都有着崇高的声望，而且是公认难度最高的会议代表。

今年全球投到STOC的论文共457篇，接收了135篇，接收率约为29%。

其中，评选出2篇最佳论文奖，以及2篇最佳学生论文奖，获奖率仅约为2.9%。最佳学生论文要求所有参与者都是博士学位以下的学生，在全球范围内“优中择优”，竞争非常激烈。即便是美国麻省理工学院、普林斯顿大学等国际一流高校的本科生也很难“上榜”。

在高手云集的最高舞台上，范致远、李嘉图与杨天祺共同完成的论文《伪随机函数的精确复杂性与计算复杂性理论中自举现象的黑盒自然证明障碍》突出重围，实属不易。

这篇论文的研究是开创性的。论文研究了伪随机函数的电路复杂性，在多个重要的电路复杂性类中对伪随机函数给出了紧的上界与下界。这些上下界结果为电路复杂性理论提供了新的理解，也解释了为何一些广为相信的猜想难以被证明。

据《中国科学报》了解，这三名同学并非从一开始就在一个团队。最初的思想雏形由李嘉图和杨天祺提出。

在大一下学期，世界著名计算机科学家、中国科学院院士姚期智讲授的计算机应用数学课程，让李嘉图和杨天祺获益匪浅。“我们认识到计算机科学是一个会产生许多有趣的、需要灵感和经验才能解决的问题的学科。”

为了汲取更多关于计算机科学的知识，他们在大一下学期提前选修段然老师的计算理论课程。正是这门课程，使他们了解到计算复杂性这一领域有着许多悬而未决的难题，也有许多刚刚起步、需要进一步探索的方向。

两人在课后查阅各种相关文献，除了想弥补知识的不足，也想找到目标方向。那段时间，他们一起翻看了近些年电路复杂性理论的一个重要突破，即麻省理工学院教授Ryan Williams提出的，证明电路复杂度下界（circuit lower bound）的算法方法（algorithmic approach）。

“我们想要从一个电路复杂度理论的前沿问题入手，了解这个领域的背景、主要技术，以及目前的重要问题。”李嘉图在接受《中国科学报》采访时表示。

不过，实际进展并不尽如人意。经过一番学习，两人虽然大致明白了这一方法的基本理论，但并没有找到可以进一步探究的问题。

2021年春季学期，他们选修了陈一镭老师讲授的密码学基础课程后，忽然感觉“柳暗花明”。

“我俩在学习中想到，是否可以将密码学与我们之前研究的电路复杂度问题联系起来，通过电路复杂度的技术研究构建密码系统所需计算资源的多少，以完成课程要求的final project。”李嘉图说。

所有选修该课程的同学都要以小组为单位，在课上作final project的报告。恰好，范致远也选修了这门课程，他在听完李嘉图和杨天祺的报告后，主动找到两人，并提出这个结果还可以有很大的改进空间。

“在范致远加入之前，我们当时仅仅针对一个电路模型得到了复杂度下界，结果较弱，技术也比较繁杂，主要为后续研究指出了一个模糊的方向。”杨天祺告诉《中国科学报》。

范致远的出现犹如及时雨，不仅提出改进意见，还大大增加了李嘉图和杨天祺对解决这一问题的信心。

“2+1”组合成团后优势互补、实力大增。

“我们三个人的合作氛围很舒服，大家经常交流和探讨，思想会碰撞出很多火花。后来，我们对原方法进行了大幅度的简化和改进，而且用完全不同的技术探索了这一问题的更多侧面。”范致远告诉《中国科学报》。

相关研究有了质的飞跃，以至于在最终的论文中，原先预设的问题甚至不再是最主要的结果，而最后展示的结果也特别出彩——在三个模型中证明了上下界。

姚班：“大神”聚集地

在这届STOC接收的135篇论文里，有7篇出自姚班师生。而在历届STOC接收的论文里，也频现姚班师生的身影，比如2020年就有4篇，2021年有3篇。

上一个获STOC最佳学生论文奖的中国人是陈立杰，他也是从姚班毕业。如今他在麻省理工学院深造，上文中提到的Ryan Williams正是他的导师。

在许多姚班学生心里，陈立杰是他们学习的榜样，是“bug”一样的存在：他获得2011年亚太地区信息学奥林匹克竞赛金牌，是2013年国际信息学奥林匹克竞赛第1名，而且是国内第一个在FOCS上发论文的本科生，后来在2019年还拿到了FOCS最佳学生论文奖，已然是理论计算机领域非常耀眼的新星。

可以说，姚班对计算机科学领域贡献巨大。

截至2021年12月，姚班学生在本科期间发表的论文有358篇，作为论文通讯作者或主要完成人的有277篇，并有121人次在FOCS、STOC、SODA、NIPS、COLT、CVPR、AAAI、ICLR等国际顶级会议上作大会报告。

这不禁让人好奇，到底是一个怎样的“神秘组织”，竟然能集结如此多的“大神”？

姚班全称是“清华学堂计算机科学实验班”，隶属于清华大学交叉信息研究院（以下简称交叉信息院），由姚期智院士一手创办。

这个全球最顶尖的精英班，入选学生都是学霸中的学霸。他们大多都是数学竞赛、物理竞赛以及信息学竞赛的金牌获得者，或者各省高考状元等，多以保送或自主招生的方式加入姚班。

像范致远、李嘉图和杨天祺，三人都是以保送方式进入清华大学，再经过层层选拔进入姚班。其中，范致远在第34届全国青少年信息学奥林匹克竞赛中拿到金牌；李嘉图和杨天祺在第35届全国青少年信息学奥林匹克竞赛中拿到金牌。

在万里挑一的姚班，身边都是清华里尖子生，所有的核心课程都是全英文授课，不做“拼命三郎”很容易落在后面。这里学术氛围非常浓厚，学生们互相切磋，寝室里的每个角落都可能成为讨论交流的地方。

范致远、李嘉图和杨天祺都是理论基础很强，且对学术研究很有兴趣，三人在姚班都十分刻苦。他们认为这次获得最佳学生论文奖，除了自身的努力，还离不开一位“大师”的支持和鼓励。

“姚先生对我们的影响是巨大的，他犹如我们前进路上的灯塔。”杨天祺说。

他和李嘉图在前期大量阅读国内外论文时，也曾对所走之路感到迷茫。“当时完全不知道从哪里下手，脑子里一堆知识，思维很混乱。”

俩人鼓起勇气主动找姚期智院士谈心。“姚先生对我们通过阅读论文学习的方法表示赞赏，也指出作为新手想要从前沿论文中直接找到可以下手的问题确实非常困难。”

“另一方面，姚先生认为我们靠之前的学习已经有了一定的知识储备，应当上手尝试解决一些问题，积累做研究的经验。”李嘉图说，“因此，他建议我们研究‘显式复杂度下界’这一问题。”

该建议立马让俩人眼前一亮。要知道，这个问题非常有名，是电路复杂度这一领域最早也是最根本的问题。

不仅如此，它还是该领域令人抓狂的难题。从上世纪50年代到现在，关于这个问题还没有任何根本性的进展，并且许多对已有结果的改进都非常繁杂。该问题上一次被改进是2016年，再上一次则要追溯到上世纪80年代。

往往越复杂的问题，处理的办法越简单。正因为对这一问题人们没有根本性的新认识，所以对已有结果的改进或许并不依赖于复杂的技术，可能更需要的是简单的灵感和细致的分类讨论。

“也就是说，不需要太多背景知识。这对我们这样的新手来说非常适合。”杨天祺表示。

值得一提的是，李嘉图和杨天祺对该问题的研究形成的论文，也被这届STOC接收了。这为他们在电路复杂度这一领域积累了经验，也是完成这篇最佳学生论文的一个相当重要的基础。