清华姚班出身，95 后博士生陈立杰获理论计算机顶会最佳学生论文

新智元

人工智能话题下的优秀答主

【新智元导读】理论计算机科学领域最顶级的国际会议 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) 电路。
本文还证明了与上述两个结果相似的成果 (例如，ACC0 和 CC0)。

目前，陈立杰在 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 上发表文章，同时也提出了一个关于相关问题的猜想，并前往纽约会场做了两篇口头报告。

大三下学期，陈立杰前往 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 教授也有三位博士生在思考这个问题，但思考了一年也没有解决。

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

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

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