理論計算機科學領域最頂級的國際會議STOC最佳學生論文獎，頒給清華姚班畢業(yè)生、MIT陳立杰等人，陳立杰在中學、大學本科階段，創(chuàng)造了無數(shù)神話，連清華大學老師都直呼他是“神人”。

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的超多項式下界的結果之間的差距，可以總結為根據(jù)線圈數(shù)量的bound n1+c^-d里的常數(shù)c＞1。

本文的成果分別改進了前人的兩種方法，他們假設涉及到N1+c/d線(而不是N1+c^-d)電路。

本文還證明了與上述兩個結果相似的成果(例如，ACC0和CC0)。

目前，陳立杰在MIT讀博，研究方向為計算復雜性理論和細粒度復雜度理論。

陳立杰在中學、大學本科階段，創(chuàng)造了無數(shù)神話，連清華大學老師都直呼他是“神人”：

2011亞太地區(qū)信息學奧林匹克競賽金牌；

2013全國信息學冬令營全場第1名；

2013國際信息學奧林匹克競賽第1名；

第一個在計算機科學基礎年會上發(fā)文的中國本科生；

2016年清華特等獎學金獲得者。

今天，讓我們一起回顧陳立杰的少年成名史。

曾是“網(wǎng)癮少年”，高三拒掉Google實習

陳立杰并非從小就是優(yōu)等生。

初中時的陳立杰喜歡做的事情和一般學生很像，無非就是玩電腦游戲，看看動漫，曾經(jīng)游戲兩三天不出門，甚至參加了數(shù)學競賽也沒有取得什么好成績，其他科目成績也不出眾。那時候的他，可以說跟“優(yōu)等生”毫不沾邊。

他唯一的愛好就是計算機。他在初中就開始學習編程，憑個人興趣參加信息學競賽。不過，初三的信息學奧賽他名落孫山，其他科目的學習成績也一落千丈，這無疑是一個巨大的打擊！

父母都勸他放棄，但他還是堅持下來了。

學習編程往往需要不斷地試錯，陳立杰在編程學習過程中，付出了巨大的試錯成本，但他沒有放棄，就像調試程序，一個成功的程序往往需要無數(shù)次的試錯，才會成功。

后來他在公開場合發(fā)言聊起過他的初三歲月，他是這么說的：

我還依稀記得，在我初三的時候，晚上我的一個好朋友在用手機跟女同學聊天，而我在用手機看OI和ACM的題目。

自習課上我的那個朋友跟女同學一起學習，而我則翹課想去機房，有時候機房老師不讓我去，我就跑去天臺用草稿紙想題目。

中午的時候我的那個朋友去跟女同學一起吃飯了，而我在機房里啃泡面。周末他們出去看電影逛公園，我就在電腦前面刷出一整版的WA（wrong answer）。

就這樣日子悠悠的過去，我的朋友如今跟女同學過得很幸福，不過我覺得我跟我的電腦得的要更加幸福。

之后的日子，陳立杰開始成天對著電腦卻再也沒有玩過游戲，所有的節(jié)假日都在認真學習，仿佛是武林高手“閉關修煉”，等待著一鳴驚人！

他的“閉關”持續(xù)到了高中，他的高中老師萬春彬給了他日常課時請假的權利，他把自己關在機房，上“Verycd”等網(wǎng)站看各類教程，然后做題、實踐，遇上不懂的內容或者做不出來的題目，就在網(wǎng)上找計算機高手解答，他還因此認識不少高手。

努力沒有白費，就像開了外掛一樣，陳立杰斬獲了國內外信息競賽多項大獎：

2010年8月，全國信息學競賽在線賽全場第2名。

2010年11月，全國信息學聯(lián)賽浙江賽區(qū)一等獎。

2011年5月，亞太地區(qū)信息學奧林匹克競賽金牌；

2011年5月，中國隊選拔賽，非集訓隊第2名。

2011年11月，全國信息學聯(lián)賽浙江賽區(qū)第1名。

2013年2月，全國信息學冬令營全場第1名。

2013年7月，國際信息學奧林匹克競賽第1名。

下圖左一為陳立杰

2011年，剛剛高一陳立杰，憑借各種信息競賽的榮譽被清華大學提前錄取了，在高三時候，谷歌發(fā)來工作邀請，希望陳立杰能去實習，但陳立杰以學習為由拒絕了。

拿獎拿到思考人生：這是我想要的生活嗎？

2013年，陳立杰進入清華大學交叉信息學院，開始了大學生涯。但在進入清華大學之后，跟很多大一新生一樣，陳立杰也陷入了迷茫。

“我作為曾經(jīng)的信息學競賽世界冠軍，頂著光環(huán)、壓力進入清華。在我的老本行算法競賽，盡管我取得了一些成績，但是當我站在領獎臺上，我經(jīng)常會想，這是我想要的生活嗎？我也偶爾會去工業(yè)界實習，但是我依然無法達到我自己真的興趣?！?/p>

與此同時，陳立杰的室友范浩強在大一軍訓期間，晚上靠“加班”完成了自己的第一篇學術論文，并最終發(fā)表在國際計算機視覺大會ICCV 2013 上（范浩強是清華姚班2013級另一位大神，后來成為曠視工號前十員工，此處不詳述）。

范浩強

室友范浩強的表現(xiàn)也給陳立杰帶來影響，他苦惱的時候經(jīng)常到紫荊操場獨自散步，思考“我是誰”、“我要做什么”這種現(xiàn)在看起來是段子，但當時卻讓陳立杰始終無法悟透的哲學問題。

一次偶然的機會，他去旁聽了唐平中教授給高年級學生講的《博弈論》，沒想到這門課程的課程論文給陳立杰打開了學術初探的大門，他也開始逐漸從競賽狀態(tài)轉向科研狀態(tài)。

博弈論又被稱為對策論（Game Theory），既是現(xiàn)代數(shù)學的一個新分支，也是運籌學的一個重要學科。

后來，在唐平中教授指導下，陳立杰完成了第一篇學術論文，是基于圖靈機視角的對囚徒困境的探索，這篇論文成為了他探索科研的第一步。

作者在論文中研究了限制條件對無窮次重復博弈納什均衡集的影響，證明了限制智能體的計算資源會導致新的納什均衡。

論文題為《受限圖靈機的有限理性》（Bounded rationality of restricted Turing machines），后被AAAI 2017接收。

“完成論文之后我非常激動，我感到我的科研興趣被點燃了，我想要嘗試更多的科研方向?！标惲⒔艿目蒲信统晒麖拇艘话l(fā)不可收拾。

后來的事實證明，陳立杰選擇的科研這條路走對了。

到了大二，在完成了姚班課程的同時，陳立杰也選修了一門非常高深的研究生課程《高等理論計算機科學》。這門課為全英文授課，要求選課同學有良好的數(shù)學基礎、以及基本的理論計算機基礎。

課程主講人李建老師布置了很多非常有挑戰(zhàn)性的問題，陳立杰每周要投入20個小時來研究，期末考試更是持續(xù)了整整24個小時，完成了十頁的答卷。

最終的成績下來，陳立杰取得了所有學員中唯一的最高分——100分，（該課程滿分為80分，其中20分是Bonus）。

陳立杰大學成績單

上了這門課之后，陳立杰的興趣完全被點燃了。

“我想，對，我是陳立杰，我要成為一名理論計算機科學家！”

首位在計算機科學基礎年會上發(fā)文的中國本科生

興趣是最好的老師。

到了大三，陳立杰開始取得了一些“微小的成就”，他首次在理論計算機科學領域頂級的國際會議COLT 2016上發(fā)表文章，同時也提出了一個關于相關問題的猜想，并前往紐約會場做了兩篇口頭報告。

陳立杰在COLT 2016上發(fā)表的論文

大三下學期，陳立杰前往MIT交換學習，師從量子信息著名學者Scott Aaronson教授。在MIT期間，陳立杰做了件非常了不起的事（以下高能）：

零知識證明(zeroknowledgeproofssystems)在密碼學理論和復雜度理論中都有著非常重要的地位。具體來講，在一個零知識證明系統(tǒng)中，一個證明者要向一個驗證者在證明一個命題的正確性的同時，不能讓驗證者獲得除了這個命題的正確性以外的任何信息。而其中要求最苛刻的被稱為統(tǒng)計零知識證明系統(tǒng)(statisticalzeroknowledgeproofssystems，簡稱SZK)。

2002年，當時著名的量子信息學者JohnWatrous教授提出計算復雜性領域的一個重要難題。JohnWatrous教授構造了一個統(tǒng)計零知識證明系統(tǒng)和量子算法在多項式時間內可以計算的問題的集合之間的喻示分割，說明了并不存在一個量子的黑盒算法可以破解統(tǒng)計零知識證明系統(tǒng)。在很多情況下，如果將量子力學的法則稍作修改，就可能得具有更強大的計算能力的計算復雜度類，但這些復雜度類基本都包含于PP之中，PP代表多項式時間內可以以嚴格大于1/2的概率計算正確的問題的集合，可見復雜度類PP是量子算法在多項式時間內可以計算的問題的集合的一個最自然的拓展。

統(tǒng)計零知識證明原理

這個問題是也是陳立杰的導師Scott Aaronson教授從2002年就開始在思考，同時Scott Aaronson教授也有三位博士生在思考這個問題，但思考了一年也沒有解決。

陳立杰對這個問題非常感興趣，苦苦思考了兩個星期，卻一直沒有進展。直到有一天，他在波士頓的街頭漫步，突然看到天空中飛過一只白鴿，它以不同的方向穿越了天空。他突然靈光一閃，想到，對，為什么不使用新的方法呢？于是他立馬沖回住處，思考了一個禮拜，終于解決了這個問題，cott Aaronson教授還專門發(fā)文章表演陳立杰。

陳立杰與合作者在論文中給出了一個統(tǒng)計零知識證明系統(tǒng)和PP的喻示分割(Oracle Separation)，這代表了PP中沒有一個黑盒算法(black box algorithm) 可以解決統(tǒng)計零知識證明系統(tǒng)中的全部問題。換句話說，他們證明即使有比量子計算（對應BQP）更強計算能力的計算機（對應PP），依然沒有一種黑盒算法可以解決統(tǒng)計零知識證明系統(tǒng)中的所有問題。

論文最后被計算機科學基礎年會（FOCS 2017）接收，陳立杰也成為首位在計算機科學基礎年會上發(fā)文的中國本科生。

有生之年能看到P=NP被解決

到大四畢業(yè)前，陳立杰就已經(jīng)在國際會議上發(fā)表了四篇學術論文，一篇文章還獲得ISAAC會議最佳學生論文獎。

2017年，陳立杰被麻省理工學院錄取，攻讀計算機博士學位，師從Ryan Williams副教授。Ryan Williams也是一位大牛，今年只有40歲，但已經(jīng)做了五年斯坦福教授。

這之后，陳立杰又發(fā)表學術會議論文近10篇，并在多個學術研討會做過學術報告。

更難能可貴的是，陳立杰非常愿意跟同學們一起討論。在他的帶領下，姚班有好幾個同學都立志做理論計算機科學。當然，科研不是單打獨斗，陳立杰跟很多姚班同學都有合作。在2016年清華特等獎的現(xiàn)場答辯中，陳立杰展示了一張”姚班論文合作網(wǎng)絡“。

他說，在姚班，已經(jīng)有三十三個同學發(fā)表了二十三篇paper！

在答辯評委提問環(huán)節(jié)，評委問他：你說想解決計算機科學領域的核心問題 P=NP ？

陳立杰：對，是這樣子的?。ㄕ坡暎?/p>

評委：你有想法了嗎？現(xiàn)在為了解決這個問題提了很多方案，你有想法了嗎？

陳立杰：是這樣子的，這個問題已經(jīng)困擾了計算機學界，可以說是從計算機這個領域一開始以來就有的問題。我現(xiàn)在作為一個大四的學生，可能確實暫時還沒什么想法，但我相信隨著我的知識的拓展，在我有生之年我能夠看到這個問題的解決。（掌聲）

姚班的開山鼻祖姚期智先生一句話，“現(xiàn)在是計算機科學的黃金時代，也是全人類的黃金時代”。

陳立杰說：能夠生在這樣一個黃金時代里，我感到無比的榮幸，我夢想能夠成為黃金時代浪潮中的一朵浪花，為人類的智慧添磚加瓦！

”我是陳立杰，我要成為一名理論計算機科學家！“