理论计算机顶会最佳学生论文出炉：清华姚班毕业高三曾拒谷歌实习

2019-03-23 14:39发布

站内文章 / 移动开发

74 0

别忘想泡老子

女 | 书童

私信

【新智元导读】理论计算机科学领域最顶级的国际会议STOC最佳学生论文奖，颁给清华姚班毕业生、MIT陈立杰等人，陈立杰在中学、大学本科阶段，创造了无数神话，连清华大学老师都直呼他是”神人“。

95后的理论计算机科学家来了。

3月15日，理论计算机科学领域最顶级的国际会议STOC 2019会议DannyLewin最佳学生论文奖揭晓，获奖论文作者为来自麻省理工学院的陈立杰和来自Weizmann Institute的Roei Tell。

ACM计算理论年会（STOC）在整个计算机科学领域享有崇高的声望，属于公认难度最高的会议之一。

获最佳学生论文奖的陈立杰出生于1995年，在中学时代参加信息竞赛并斩获多项Top奖项，2011年被清华大学交叉信息学院提前录取，就读姚班。

陈立杰

陈立杰等人的论文题目Bootstrapping Results for Threshold Circuits “Just Beyond” KnownLower Bounds。

论文中主要工作结论是：

当前已知的结果与足以得到TC0的超多项式下界的结果之间的差距，可以总结为根据线圈数量的bound n1+c^-d里的常数c＞1。
本文的成果分别改进了前人的两种方法，他们假设涉及到N1+c/d线(而不是N1+c^-d)电路。
本文还证明了与上述两个结果相似的成果(例如，ACC⁰和CC⁰)。

目前，陈立杰在MIT读博，研究方向为计算复杂性理论和细粒度复杂度理论。

陈立杰在中学、大学本科阶段，创造了无数神话，连清华大学老师都直呼他是“神人”：

2011亚太地区信息学奥林匹克竞赛金牌；
2013全国信息学冬令营全场第1名；
2013国际信息学奥林匹克竞赛第1名；
第一个在计算机科学基础年会上发文的中国本科生；
2016年清华特等奖学金获得者。

今天，让我们一起回顾陈立杰的少年成名史。

曾是“网瘾少年”，高三拒掉Google实习

陈立杰并非从小就是优等生。

初中时的陈立杰喜欢做的事情和一般学生很像，无非就是玩电脑游戏，看看动漫，曾经游戏两三天不出门，甚至参加了数学竞赛也没有取得什么好成绩，其他科目成绩也不出众。那时候的他，可以说跟“优等生”毫不沾边。

他唯一的爱好就是计算机。他在初中就开始学习编程，凭个人兴趣参加信息学竞赛。不过，初三的信息学奥赛他名落孙山，其他科目的学习成绩也一落千丈，这无疑是一个巨大的打击！

父母都劝他放弃，但他还是坚持下来了。

学习编程往往需要不断地试错，陈立杰在编程学习过程中，付出了巨大的试错成本，但他没有放弃，就像调试程序，一个成功的程序往往需要无数次的试错，才会成功。

后来他在公开场合发言聊起过他的初三岁月，他是这么说的：

我还依稀记得，在我初三的时候，晚上我的一个好朋友在用手机跟女同学聊天，而我在用手机看OI和ACM的题目。

自习课上我的那个朋友跟女同学一起学习，而我则翘课想去机房，有时候机房老师不让我去，我就跑去天台用草稿纸想题目。

中午的时候我的那个朋友去跟女同学一起吃饭了，而我在机房里啃泡面。周末他们出去看电影逛公园，我就在电脑前面刷出一整版的WA（wrong answer）。

就这样日子悠悠的过去，我的朋友如今跟女同学过得很幸福，不过我觉得我跟我的电脑得的要更加幸福。

之后的日子，陈立杰开始成天对着电脑却再也没有玩过游戏，所有的节假日都在认真学习，仿佛是武林高手“闭关修炼”，等待着一鸣惊人！

他的“闭关”持续到了高中，他的高中老师万春彬给了他日常课时请假的权利，他把自己关在机房，上“Verycd”等网站看各类教程，然后做题、实践，遇上不懂的内容或者做不出来的题目，就在网上找计算机高手解答，他还因此认识不少高手。

努力没有白费，就像开了外挂一样，陈立杰斩获了国内外信息竞赛多项大奖：

2010年8月，全国信息学竞赛在线赛全场第2名。
2010年11月，全国信息学联赛浙江赛区一等奖。
2011年5月，亚太地区信息学奥林匹克竞赛金牌；
2011年5月，中国队选拔赛，非集训队第2名。
2011年11月，全国信息学联赛浙江赛区第1名。
2013年2月，全国信息学冬令营全场第1名。
2013年7月，国际信息学奥林匹克竞赛第1名。

左一为陈立杰

2011年，刚刚高一陈立杰，凭借各种信息竞赛的荣誉被清华大学提前录取了，在高三时候，谷歌发来工作邀请，希望陈立杰能去实习，但陈立杰以学习为由拒绝了。

拿奖拿到思考人生：这是我想要的生活吗？

2013年，陈立杰进入清华大学交叉信息学院，开始了大学生涯。但在进入清华大学之后，跟很多大一新生一样，陈立杰也陷入了迷茫。

“我作为曾经的信息学竞赛世界冠军，顶着光环、压力进入清华。在我的老本行算法竞赛，尽管我取得了一些成绩，但是当我站在领奖台上，我经常会想，这是我想要的生活吗？我也偶尔会去工业界实习，但是我依然无法达到我自己真的兴趣。”

与此同时，陈立杰的室友范浩强在大一军训期间，晚上靠“加班”完成了自己的第一篇学术论文，并最终发表在国际计算机视觉大会ICCV 2013 上（范浩强是清华姚班2013级另一位大神，后来成为旷视工号前十员工，此处不详述）。

范浩强

室友范浩强的表现也给陈立杰带来影响，他苦恼的时候经常到紫荆操场独自散步，思考“我是谁”、“我要做什么”这种现在看起来是段子，但当时却让陈立杰始终无法悟透的哲学问题。

一次偶然的机会，他去旁听了唐中平教授给高年级学生讲的《博弈论》，没想到这门课程的课程论文给陈立杰打开了学术初探的大门，他也开始逐渐从竞赛状态转向科研状态。

博弈论又被称为对策论（Game Theory），既是现代数学的一个新分支，也是运筹学的一个重要学科。

后来，在唐平中教授指导下，陈立杰完成了第一篇学术论文，是基于图灵机视角的对囚徒困境的探索，这篇论文成为了他探索科研的第一步。

作者在论文中研究了限制条件对无穷次重复博弈纳什均衡集的影响，证明了限制智能体的计算资源会导致新的纳什均衡。

论文题为《受限图灵机的有限理性》（Bounded rationality of restricted Turing machines），后被AAAI 2017接收。

“完成论文之后我非常激动，我感到我的科研兴趣被点燃了，我想要尝试更多的科研方向。”陈立杰的科研努力和成果从此一发不可收拾。

后来的事实证明，陈立杰选择的科研这条路走对了。

到了大二，在完成了姚班课程的同时，陈立杰也选修了一门非常高深的研究生课程《高等理论计算机科学》。这门课为全英文授课，要求选课同学有良好的数学基础、以及基本的理论计算机基础。

课程主讲人李建老师布置了很多非常有挑战性的问题，陈立杰每周要投入20个小时来研究，期末考试更是持续了整整24个小时，完成了十页的答卷。

最终的成绩下来，陈立杰取得了所有学员中唯一的最高分——100分，（该课程满分为80分，其中20分是Bonus）。

陈立杰大学成绩单

上了这门课之后，陈立杰的兴趣完全被点燃了。

“我想，对，我是陈立杰，我要成为一名理论计算机科学家！”

首位在计算机科学基础年会上发文的中国本科生

兴趣是最好的老师。

到了大三，陈立杰开始取得了一些“微小的成就”，他首次在理论计算机科学领域顶级的国际会议COLT 2016上发表文章，同时也提出了一个关于相关问题的猜想，并前往纽约会场做了两篇口头报告。

陈立杰在COLT 2016上发表的论文

大三下学期，陈立杰前往MIT交换学习，师从量子信息著名学者Scott Aaronson教授。在MIT期间，陈立杰做了件非常了不起的事（以下高能）：

零知识证明(zero knowledge proofs systems)在密码学理论和复杂度理论中都有着非常重要的地位。具体来讲，在一个零知识证明系统中，一个证明者要向一个验证者在证明一个命题的正确性的同时，不能让验证者获得除了这个命题的正确性以外的任何信息。而其中要求最苛刻的被称为统计零知识证明系统(statistical zero knowledge proofs systems，简称SZK)。

2002年，当时著名的量子信息学者John Watrous教授提出计算复杂性领域的一个重要难题。John Watrous教授构造了一个统计零知识证明系统和量子算法在多项式时间内可以计算的问题的集合之间的喻示分割，说明了并不存在一个量子的黑盒算法可以破解统计零知识证明系统。在很多情况下，如果将量子力学的法则稍作修改，就可能得具有更强大的计算能力的计算复杂度类，但这些复杂度类基本都包含于PP之中，PP代表多项式时间内可以以严格大于1/2的概率计算正确的问题的集合，可见复杂度类PP是量子算法在多项式时间内可以计算的问题的集合的一个最自然的拓展。

统计零知识证明原理

这个问题是也是陈立杰的导师Scott Aaronson教授从2002年就开始在思考，同时Scott Aaronson教授也有三位博士生在思考这个问题，但思考了一年也没有解决。

陈立杰对这个问题非常感兴趣，苦苦思考了两个星期，却一直没有进展。直到有一天，他在波士顿的街头漫步，突然看到天空中飞过一只白鸽，它以不同的方向穿越了天空。他突然灵光一闪，想到，对，为什么不使用新的方法呢？于是他立马冲回住处，思考了一个礼拜，终于解决了这个问题，cott Aaronson教授还专门发文章表演陈立杰。

陈立杰与合作者在论文中给出了一个统计零知识证明系统和PP的喻示分割(Oracle Separation)，这代表了PP中没有一个黑盒算法(black box algorithm) 可以解决统计零知识证明系统中的全部问题。换句话说，他们证明即使有比量子计算（对应BQP）更强计算能力的计算机（对应PP），依然没有一种黑盒算法可以解决统计零知识证明系统中的所有问题。

论文最后被计算机科学基础年会（FOCS 2017）接收，陈立杰也成为首位在计算机科学基础年会上发文的中国本科生。