一位冉冉上升的青年理论计算机科学家：陈立杰斩获ACM STOC最佳学生论文

雷锋网 AI 科技评论按：前不久我们刚刚介绍了 出自清华姚班并获得 2019 年斯隆研究奖的华裔学者鬲融 ，近日我们又获悉另一位姚班天才少年 陈立杰 获得 ACM STOC 2019 最佳学生论文奖殊荣。我国的青年学者真是人才辈出啊。

2018 年下半年，陈立杰做学术报告，题目为《Recent Structure Lemmas for Depth-Two Threshold Circuits》

ACM STOC （Symposium on Theory of Computing，计算理论年会）是理论计算机科学领域最顶级的国际会议，在整个计算机科学领域享有崇高的声望，并被公认属于难度最高的会议之一。ACM STOC 2019 将于今年 6 月 23 至 26 日在美国亚利桑那州菲尼克斯举行，届时陈立杰将进行现场报告并和论文第二作者、来自 Weizmann Institute 的 Roei Tell 共同上台领取「Danny Lewin」最佳学生论文奖。

此次陈立杰的获奖论文是《Bootstrapping Results for Threshold Circuits “Just Beyond” KnownLower Bounds》（ https://eccc.weizmann.ac.il/report/2018/199/ ）。 由于我们编辑们在这方面的学术水平过于浅薄，就不做更详细的介绍了，欢迎感兴趣的读者自行翻阅原文。 但对于陈立杰来讲，他不仅在读博前就发表过论文，甚至在读博前就拿到过顶级学术会议的论文奖。

陈立杰个人履历

陈立杰在 MIT 个人主页的照片

陈立杰很早就对计算机产生了兴趣，也曾参加 TopCoder  和 Codeforces 编程比赛。在吸收越来越多的知识、经历越来越多的锻炼之后，陈立杰也逐渐明确了自己的兴趣是理论计算机科学方向。

2013 年，陈立杰高三，参加第 25 届国际信息学奥林匹克竞赛并以第一名成绩获得金牌，同年保送清华大学交叉信息学院姚班。在清华大学期间，陈立杰的指导教师是清华大学交叉信息研究院副教授、博士生导师李建教授，围绕 Multi-Armed Bandits 问题做了一些研究。

2016 年春季，陈立杰到 MIT 做学术访问，在德克萨斯大学奥斯汀分校计算机科学教授 Scott Aaronson 指导下研究量子复杂性（Quantum Complexity）问题。

整个本科期间，陈立杰不仅专业课成绩几乎都是满分，更以第一作者身份发表多篇学术论文，包括：

• ISAAC 2016 论文一篇，并获最佳学生论文奖（International Symposium on Algorithms and Computation，算法和计算国际会议，A 级会议）。值得注意的是，此时的陈立杰只是本科生，但已经 PK 赢了许多在读博士生，取得了最佳学生论文奖。

• AAAI 2017 论文 1 篇（我们都熟悉的人工智能顶级会议，A+ 级）

• COLT 论文 4 篇（Annual Conference on Learning Theory，ACM 主办，计算学习理论顶级会议，A+ 级会议）；其中一篇解决了 COLT 会议遗留已久的一个开放性问题，此问题由著名量子信息学者 John Watrous 在 2002 年提出。

• 另外还有 AAMAS、AISTATS、CCC、FOCS 等会议论文若干篇
  

2017 年，已经是理论计算机领域耀眼新星的陈立杰被麻省理工学院录取，攻读计算机博士学位，师从 Ryan Williams，研究方向为计算复杂性理论和细粒度复杂度理论。这之后陈立杰又发表学术会议论文近 10 篇，其中就包括此次 ACM STOC 2019 的最佳学生论文奖获奖论文。

陈立杰曾在多个学术研讨会进行过学术报告，2018 年秋季还前往 UC 伯克利的 SIMONS 研究院做访问学者。此外雷锋网 AI 科技评论了解到，陈立杰还长期参与中国信息学竞赛的组织和命题工作。

（陈立杰的论文清单可以参见他的个人主页 https://www.mit.edu/~lijieche/papersYear.html ）

陈立杰清华特等奖答辩回顾

除了我们上面的总结，陈立杰本人也曾在 2016 年清华特等奖的现场答辩中总结了自己本科期间的主要表现。我们一起来回顾一下。

首先由候选人的介绍人、也是陈立杰的指导老师，交叉信息研究院助理教授李建进行简单的介绍：

今天很荣幸向大家介绍姚班大四的学生陈立杰同学，陈立杰同学在高中阶段就获得了国际信息学竞赛世界第一名，不光是金牌，还是世界第一，顺利保送清华来到姚班。在大学三年中，他的学习成绩也是不断进步，从第一年的第九，到第二年的第二，再到第三年的第一名，他修够了我教的 研究生的《高等理论计算机课程》 ，他得了110分，其中有十几分的 bonus problem。

他的学习成绩和竞赛成绩已经非常辉煌，但是我作为一个理论计算机学者，他最让我感到印象深刻的是他这两年在理论计算机科学方面所取得的成绩。短短两年期间，他已经成长成一个 非常年轻，但是已经有独立寻找问题能力、并解决非常困难问题能力的一个年轻的理论计算机科学家 。

陈立杰在 MIT 交换期间，独立解决了 2002 年由著名量子信息论学者 Scott Aaronson 和 John Watrous 提出的十几年悬而未决的问题。陈立杰同学完全解决，paper 已经提交到计算机科学理论最权威的会议 STOC 2017。 陈立杰同学还做了其他几个很有重量的结果，接下来他自己会介绍。

陈立杰同学还有另外一个非常难能可贵的地方，就是他非常愿意跟同学们一起讨论，在他的带领下， 姚班有好几个同学都立志做理论计算机科学 （掌声）。我非常期待陈立杰和他的小伙伴们能够在这个方面取得更大的成就，将来成为理论计算机科学顶级的科学家。

接着，陈立杰走上讲台开始报告：

非常感谢李老师的介绍，大家好，我是交叉信息研究院的陈立杰，今天非常有幸作为清华万千奋斗者中的一员，来讲讲我自己的科研经历。

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

到了大二，在竞赛和实习之余，一次偶然的机会，我上了一门姚班高年级课程《博弈论》，没想到这门课程的课程论文竟然成为了我的学术初探。我在唐平中教授指导下完成了第一篇学术论文，是关于图灵机和囚徒困境结合的问题。

完成论文之后我非常激动，我感到我的科研兴趣被点燃了，我想要尝试更多的科研方向。大二在还行的完成了姚班课程的同时，我也选修了一门非常高深的研究生课程《高等理论计算机科学》，这门课的主讲人就是我的介绍人李建老师，给我们布置了很多非常有挑战性的问题，我每周要投入20个小时来研究，期末考试更是持续了整整24个小时，完成了十页的答卷。我取得了唯一的最高分——一百分。上了这门课之后，我的兴趣被完全点燃了，我想， 对，我是陈立杰，我要成为一名理论计算机科学家！ （掌声）谢谢大家。

在大三的时候我取得了一些微小的成就，我的一篇文章被发表于 STOC 2016，这是国际计算机理论的顶级会议，同时我也提出了一个关于相关问题的猜想，我前往纽约会场做了 两篇口头报告 。

大三下学期我前往 MIT 师从量子信息著名学者 Scott Aaronson 教授。在 MIT，我每天花费十多个小时进行科研，我的研究既有理论方向，也有和实践结合的方向。其中一个问题是关于量子优越性，也俗称量子霸权。大家都相信量子计算机是优于普通计算机的，但是要通过合理的实验证明这一点需要相当好的理论基础。现在很多大公司，比如谷歌也投入巨大的资源来进行研究，我和我的导师 Aaronson 设计了一个关于解决这个问题的理论框架，这说明 量子计算机即将迈入工业时代，量子计算机的黎明就可以闪现了 。

在完成了这个问题之后，Aaronson 教授向我提及了一个相关的 open problem，这个问题是他在 2002 年开始就在思考，同时他也有三位博士生在思考这个问题，思考了一年也没有解决。我非常感兴趣，在这两个星期里我苦苦思索，但是却一直没有进展。直到有一天，我在波士顿的街头漫步，突然看到天空中飞过一只白鸽，它以不同的方向穿越了天空。我突然灵光一闪，想到，对， 为什么我不使用新的方法呢，于是我立马冲回我的住处，思考了一个礼拜，解决了这个问题。 （掌声）谢谢大家。

解决这个问题之后， Aaronson 教授非常激动，他亲自写了一篇博文祝贺我。 （掌声）

大三下学期我回到清华，继续拓展和发展我的研究， 目前我已经在国际会议上发表了四篇学术论文，另外有八篇在投，一篇文章还获得 ISAAC 会议最佳学生论文奖。

当然，科研不是单打独斗，就跟李老师说的一样，我跟很多姚班同学都有合作，这是我们的合作网络（见视频）。在我们班级，据悉有三十三个同学已经发表了二十三篇paper！

最后，这么多同学在科研上前仆后继，不禁让我想起了姚先生一句话， “现在是计算机科学的黄金时代，也是全人类的黄金时代”。能够生在这样一个黄金时代里，我感到无比的荣幸，我梦想能够成为黄金时代浪潮中的一朵浪花，为人类的智慧添砖加瓦！

最后，谢谢我的介绍人，谢谢照顾我的老师们，谢谢我的同学们和我的辅导员，谢谢大家。（掌声）

评委提问环节：

评委：同学，我们看到你的理想，你说想解决计算机科学领域的核心问题 P=NP ？

陈立杰：对，是这样子的！（掌声）

评委：你有想法了吗？现在为了解决这个问题提了很多方案，你有想法了吗？

陈立杰：是这样子的，这个问题已经困扰了计算机学界，可以说是从计算机这个领域一开始以来就有的问题。我现在作为一个大四的学生，可能确实暂时还没什么想法， 但我相信随着我的知识的拓展，在我有生之年我能够看到这个问题的解决。 （掌声）

评委：我是你的嫡系师兄，当年刚进贵系时我也学理论这个方向。刚刚张院士讲到，计算机非常强调应用学科，理论基础非常重要，图灵机也应用在了量子计算机、人工智能方面。我希望看到，你对贵系也好，对人类也好，有没有做一些更深的、更具体的工作？

陈立杰：具体工作的话可以看一下我的 PPT，我在做的一个成果是关于如何让量子计算机展现它的实力。大家预计在有限的未来，大概十年到五年之内，就会有 50 个比特的量子计算机，但是光使用 50 个比特是很难展现出量子计算机相对于传统计算机的实力的。想象一下，只有 50 个bit怎么编程，对吧？所以你需要设计一个非常精细的问题来给实践指明方向，我的工作就是为了给实践工业家指明方向，他们能够找到这样的问题的解法。

评委：你平常参加体育锻炼吗？主要方式是什么？

陈立杰：刚刚在视频里面就有展示我在健身房健身，我每周会去健身房三次。（掌声）

（完整视频见 https://www.bilibili.com/video/av7039211/ ）

2016 年时陈立杰兴奋地表达了自己成为理论计算机科学家的志向，如今他已经在这条路上做出越来越多的成果，对计算机理论领域产生越来越大的影响。我们在由衷敬佩的同时，也祝愿陈立杰做出更多、更影响深远的学术成果。

雷锋网 (公众号：雷锋网) AI 科技评论报道。

。