图灵奖得主姚期智院士的清华“姚班”又获大奖！

来源 | 小木虫

编辑 | 学术君

近日，根据计算机科学领域顶级国际会议第54届ACM计算理论年会（STOC 2022 54th Annual Symposium on the Theory of Computing）官网公布，交叉信息院师生及校友共有7篇论文被接收，其中计科班91班范致远、计科92班李嘉图与杨天祺，三位同学共同完成的论文《The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity》被大会接收，并获评最佳学生论文。

图中分别为范致远、李嘉图和杨天祺。受访者供图

伪随机函数（pseudorandom functions）是无法与随机函数区分开的函数族。它作为密码学许多构造的起点，是密码学的基础。因此构造高效的伪随机函数在理论及应用中有多种意义。该论文研究了伪随机函数的电路复杂性，在多个重要的电路复杂性类中对伪随机函数给出了紧的上界与下界。例如证明了在一般电路中，若多项式大小的电路可计算的伪随机函数存在，则存在一个仅需大约2n个门的电路族即可计算的伪随机函数。同时，该研究无条件地证明了计算任何伪随机函数至少需要2n-2个门。

论文插图：两层线性阈门电路

这些上下界结果为电路复杂性理论提供了新的理解，也解释了为何一些广为相信的猜想难以被证明。特别地，针对目前电路复杂性理论中存在的“自举现象”（bootstrapping phenomena），该研究指出，要想从这些现象推出P vs NP等重要开放问题的答案，还需要一些全新的证明思路。

ACM计算理论年会（STOC）是理论计算机科学领域最顶级的国际会议，在整个计算机科学领域享有崇高的声望，并被公认是难度最高的会议之一。STOC2022将于意大利罗马召开，本次会议共接收论文投稿457篇，录用135篇，接收率约为29%。

清华姚班是什么神秘组织？

清华姚班——

全称“清华学堂计算机科学实验班”

由世界著名计算机科学家

唯一获得图灵奖的华人

（图灵奖：“计算机界诺贝尔奖”）

姚期智教授于2005年主导创办

配备强大国际化师资团队

采用“因材施教”和“深耕精耕”培养模式

建造多方位的高端国际学术交流平台

培养“最优秀的本科生”

实现“最优秀的本科教育”

在2018年全球大学排名中

清华姚班取代麻省理工

成为全球计算机科学专业的NO.1!

王者较量 实力登顶

中国唯一图灵奖获得者—姚期智院士

诺贝尔奖是无数科学家心中的最高奖项，是很多科研工作者一生追求的目标。但诺贝尔奖有一个局限就是没有关于计算机领域的奖项。图灵奖是目前此领域最具分量的一个奖项，我国目前只有姚期智教授获此殊荣，他堪称世界级的一位科学家。

潜 心 修 学 

姚期智祖籍是湖北，但他是在上海出生的。从小他学习成绩优异，高中毕业的时候，他毅然决然地选择了物理学。因为当时姚期智的偶像是杨振宁先生，他渴望像自己的偶像一样，在物理学领域取得非凡成就。凭借着优异的成绩，姚期智顺利入学台湾大学物理学系。从台湾大学毕业之后，姚期智选择前往美国进修，他考上了哈佛大学的研究生，并且成为了知名教授的学生。

 在哈佛大学，姚期智投入了全部的精力在物理学领域，他一举拿到了博士学位。当时众人都以为姚期智一定会在物理学领域继续研究下去，最后很有可能会超过他的导师，顺利拿到诺贝尔奖。但姚期智却做出了令人难以置信的选择，他突然转行进入了计算机领域。因为在他求学阶段，计算机技术迅猛发展，并成为当时最热门的学科。

 姚期智看到了这门学科的前景，认为只要深入研究下去，一定会有很大的收获。于是年仅二十六岁的他做出了一个大胆的决定，姚期智放弃了一直从事的物理学研究工作，转而投向了计算机领域。

 凭借自己过人的学习能力，姚期智仅用三年的时间就拿到了计算机专业的博士学位。当时姚期智还不到三十岁，但是手中已经握有两个博士学位。

斩 获 图 灵 奖 

他先后在美国麻省理工学院、斯坦福大学、加利福尼亚大学、普林斯顿大学担任教授。不同学校的办学方式以及学术资源拓展了姚期智的眼界，为他带来源源不断的灵感。在此基础上，姚式理论得到了进一步发展。他凭借独特创新的思维方式不断地冲击新的学术领域，并在科研工作者之间获得了极高的评价。

 1998年和2000年，姚期智被先后选为美国国家科学院院士和美国科学与艺术学院院士。经过三十多年的磨砺和成长，姚期智在计算理论及其在密码学和量子计算中的应用等研究方向上，已成为世界顶尖的计算机科学大师。 

在姚期智发表的上百篇论文中，他几乎完整地剖析了计算机科学的思维逻辑，并在通信复杂性的研究方向上达到了别人难以企及的高度。为了表彰姚期智在计算机科学领域的一系列贡献，美国计算机协会（ACM）授予了他2000年年度的图灵奖奖项。

归 国 任 教 

57岁那年，姚期智辞去了普林斯顿大学的终身教职，义无反顾地返回祖国怀抱成为清华大学的全职教授。 

“我是中国人，中国是我的祖国，我对中国的感情很深，现在我要永远地回来了，永远地回来。”他说。

在姚期智的主导下，“清华学堂计算机科学实验班”（姚班）2005年创立。十五年来，“姚班”培养了一批在全国乃至全世界计算机领域具有影响力的人才，姚期智对此非常满意。而超过姚期智预期的，则是计算机相关的交叉科学。他提议在清华成立交叉信息研究院：“我们把譬如量子物理、生物医学、经济金融等等的领域和计算机科学的技术结合起来。这在当时应该是一个非常先进的观念，在世界上都是很少有的。”在学校的全力支持下，交叉信息研究院很快就建立了。

随后，姚期智又把目光转向了人工智能（AI）领域。2019年5月，清华大学人工智能班（智班）成立，姚期智出任首席教授。

“中国在几十年前曾经丧失了一些和国际上同时起步的时机，我想我们现在有一个非常好的机会，在以后十年、二十年，人工智能会改变这个世界的时候，我们应该在这个时候跟别人同时起步甚至比别人更先走一步，好好培养我们的人才，从事我们的研究。”姚期智说。

本文来源：小木虫

转载本文请联系原作者获取授权，同时请注明本文来源。

如果不想错过每日精彩

一定要星标置顶哟~ ▼

后台回复关键词：福利

学术君精选

▼ 点击「阅读原文」，获取更多免费资源