国内首次！位清华姚班后学霸斩获计算机理论顶会最佳学生论文奖

国内首次！3位清华姚班00后学霸斩获计算机理论顶会最佳学生论文奖

新智元报告

艺术经纬:乔伊太困了

[新智元简介]2022年，STOC，计算机理论峰会正式开幕，三位来自清华姚班的00后学生获得最佳学生论文奖。

近日，理论计算机科学领域的顶级国际会议——第54届ACM计算理论年会(STOC 2022)拉开帷幕。

姚班三位00后学者范志远、李嘉图、杨天琦凭借《伪随机函数精确复杂性与计算复杂性理论中自举现象的黑盒自然证明障碍》获得最佳学生论文奖。

从左至右分别是范志远、李嘉图和杨天琦(来源:中国科学报)

ACM计算理论年会(STOC)是理论计算机科学领域的顶级国际会议。它在整个计算机科学领域享有很高的声誉，是公认的最难的会议之一。它与IEEE计算机科学基础年会(FOCS)并称为理论计算机科学的两次峰会。

STOC由ACM SIG Act(算法和计算理论特别兴趣小组)发起，涵盖算法和数据结构、计算复杂性、密码学、计算几何、组合学、随机化和去随机化、算法博弈论和量子计算等领域。

2022年STOC共收到457份申请，135份被接受，接受率约为29%。然后评选出两个最佳论文奖和两个最佳学生论文奖。这样算下来，胜率只有2.9%。

获得最佳论文奖的两篇论文分别来自魏茨曼科学研究所、希伯来大学和莫斯科国立大学。

获得最佳学生论文奖的两篇论文分别来自麻省理工学院、微软研究院和清华大学。

地址:https://www.youtube.com/watch? v = qcbypyg 6 omu

6月23日是三篇获奖论文的颁奖时间。

地址:https://dl.acm.org/doi/abs/10.1145/3519935.3520010

伪随机函数是一类无法与随机函数区分开来的函数。作为密码学许多构造的起点，它是密码学的基础。因此，构造高效的伪随机函数具有重要的理论和应用意义。

本文对伪随机函数的电路复杂度进行了研究，在几个重要的电路复杂度类中给出了伪随机函数的紧上下界。比如证明了在一般电路中，如果有一个伪随机函数可以用多项式大小的电路来计算，就有一个伪随机函数可以用一个只有2n个左右门的电路族来计算。同时，本研究无条件地证明了计算任何伪随机函数至少需要2n-2个门。

00后学霸:从走清华到登顶领奖。

范志远

范志远曾是南京一中有名的“化学哥”。从初三第一次接触化学实验开始，范志远就对化学产生了浓厚的兴趣，他在化学方面的天赋也逐渐显露出来。

入学几次考试，他的化学成绩都很突出。

在参加中国化学奥林匹克决赛之前，范志远和省队的伙伴们一起接受了南京大学化学老师系统的赛前训练。他四个月“攒了200页错题”。

2015年，范志远获得中国化学奥林匹克竞赛(决赛)和冬令营金牌，被清华大学化学生物学基础科学班一线录取。

2017年7月30日，范志远获得第34届全国青少年信息学奥林匹克竞赛金牌，清华大学也向他抛出了橄榄枝。

范志远顺利获得清华大学化学生物基础理科班一本线录取资格。

来看看神的获奖经历吧。

让我们看看范志远曾经就读的杭州薛军中学。获得两次世界冠军，三次国际金牌，29次亚太区金牌，23次全国金牌，259次全国联赛一等奖。

十年来，清北录取的学生已达七八十人，他们的学生遍布哈佛、麻省理工、斯坦福等国际名校，就职于谷歌、脸书、微软、百度等著名IT公司。

说“清北的摇篮”也不为过。

里卡多

李嘉图高中就读于太原五中。18年7月，李嘉图获得第35届全国青少年信息学奥林匹克竞赛金牌，进入国家集训队，获得保送清华的资格。

在2018年1月29日-2月1日举办的“清华大学全国优秀信息学中学生冬季体验营”中，清华大学计算机系邀请“213名优秀信息学奥赛生”参加全国知名高中体验营。

里卡多是山西省唯一受邀参加体验营的学生。

杨天琦

高中就读于南京师范大学附属中学，2018年全国信息学奥林匹克竞赛各省(省级赛区)一等奖，2018年全国青少年信息学奥林匹克竞赛一等奖。

2019年入选信息学国家集训队，获得清华保送资格。他的兴趣是计算复杂性，他目前专注于电路的下限。

那么这三位来自全国各地的天才少年是如何组队成功拿下最佳学生论文的呢？

事实上，这篇论文从一开始的构思，到研究团队的成立，再到成功发表获奖的过程并不是一帆风顺的。

里卡多在接受《中国科学报》采访时表示，他们三人从一开始就不在一个团队。

本文最初的概念原型是由李嘉图和杨天琦提出的。

从下学期开始，他们在姚期智院士讲授的计算机应用数学课程中收获颇丰，并提前选修了段冉老师讲授的计算理论课程。这个课程让他意识到，在计算复杂性领域，还有很多值得深耕的领域。

在那段时间里，他们查阅了近年来电路复杂性理论的一项重要突破，即麻省理工学院教授瑞恩·威廉姆斯提出的证明电路复杂性下限的算法方法。

李嘉图说，“我们想从电路复杂性理论的一个前沿问题入手，了解这个领域的背景、主要技术和重要问题”。

然而，实际进展并没有想象中那么容易。经过这方面的一些研究，两人虽然大致了解了这个理论的框架，但是并没有发现有什么值得他们研究的课题。

此时，范志远的加入，如同“及时雨”，为后续的研究指明了一个大方向。

范志远说，“我们三个人合作的氛围很舒服。我们经常交流讨论，思想会相互碰撞。后来我们对原来的方法进行了极大的简化和改进，用完全不同的技术探索了这个问题的更多方面”。

范志远的加入为团队的研究进展提供了新的动力，相关研究成果随即涌出。

在论文的最终稿中，最初预设的问题不再是最终的结果。最后，论文的陈述是成功的，即在三个模型中证明了上界和下界。

值得一提的是，李嘉图和杨天琦的另一篇论文也被STOC 2022接受。

地址:https://dl.acm.org/doi/10.1145/3519935.3519976

地址:https://www.youtube.com/watch? v = 54 il PK 6 jk5c

电路复杂性是复杂性理论中广泛关注的问题。一个经典的结论是，大多数语言需要指数规模的电路来做决定，但这个结论的证明是非建设性的。给出一个具体的语言，需要一个大的电路来判断，这是一个有几十年历史的开放性问题。

在此之前，Find、Golov Nev、Hirsch和库利科夫在2016年给出了最好的结果:存在一种多项式可计算语言，它不能用(3+1/86)n-o(n)大小的电路来计算。这项研究改进了他们的方法，证明了同一种语言不能用3.1n-o(n)大小的电路来计算。

清华:计算机天才的摇篮

清华计算机科学实验班，又名“姚班”。

因为它是由2000年图灵奖获得者、美国国家科学院院士姚期智创立的，所以被命名为“姚班”

姚班致力于培养与麻省理工学院、普林斯顿大学等世界一流大学本科生同等甚至更高竞争力的国际顶尖创新型计算机科学人才。

STOC收到的135篇论文中，有7篇来自姚班的教师和学生。

在历届STOC纸展上，姚班学生也是常客。比如2020年4篇，2021年3篇。

上一个获得STOC最佳学生论文奖的中国人是陈立杰。他也是姚班的学生之一。他目前在麻省理工学院学习。

姚班在计算机领域的地位可想而知。

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

参考资料:

https://www.tsinghua.edu.cn/info/1175/94548.htm

新闻来源:

https://mp.weixin.qq.com/s/ttwfftwpYGBV-NsIfcCX7Q