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

95后的理論計(jì)算機(jī)科學(xué)家來了。

3月15日，理論計(jì)算機(jī)科學(xué)領(lǐng)域最頂級(jí)的國(guó)際會(huì)議STOC 2019會(huì)議DannyLewin最佳學(xué)生論文獎(jiǎng)揭曉，獲獎(jiǎng)?wù)撐淖髡邽閬碜月槭±砉W(xué)院的陳立杰和來自Weizmann Institute的Roei Tell。

ACM計(jì)算理論年會(huì)（STOC）在整個(gè)計(jì)算機(jī)科學(xué)領(lǐng)域享有崇高的聲望，屬于公認(rèn)難度最高的會(huì)議之一。

獲最佳學(xué)生論文獎(jiǎng)的陳立杰出生于1995年，在中學(xué)時(shí)代參加信息競(jìng)賽并斬獲多項(xiàng)Top獎(jiǎng)項(xiàng)，2011年被清華大學(xué)交叉信息學(xué)院提前錄取，就讀姚班。

陳立杰

陳立杰等人的論文題目Bootstrapping Results for Threshold Circuits “Just Beyond” KnownLower Bounds。

論文中主要工作結(jié)論是：

當(dāng)前已知的結(jié)果與足以得到TC0的超多項(xiàng)式下界的結(jié)果之間的差距，可以總結(jié)為根據(jù)線圈數(shù)量的bound n1+c^-d里的常數(shù)c＞1。

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

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

目前，陳立杰在MIT讀博，研究方向?yàn)橛?jì)算復(fù)雜性理論和細(xì)粒度復(fù)雜度理論。

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

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

2013全國(guó)信息學(xué)冬令營(yíng)全場(chǎng)第1名；

2013國(guó)際信息學(xué)奧林匹克競(jìng)賽第1名；

第一個(gè)在計(jì)算機(jī)科學(xué)基礎(chǔ)年會(huì)上發(fā)文的中國(guó)本科生；

2016年清華特等獎(jiǎng)學(xué)金獲得者。

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

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

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

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

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

父母都勸他放棄，但他還是堅(jiān)持下來了。

學(xué)習(xí)編程往往需要不斷地試錯(cuò)，陳立杰在編程學(xué)習(xí)過程中，付出了巨大的試錯(cuò)成本，但他沒有放棄，就像調(diào)試程序，一個(gè)成功的程序往往需要無數(shù)次的試錯(cuò)，才會(huì)成功。

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

我還依稀記得，在我初三的時(shí)候，晚上我的一個(gè)好朋友在用手機(jī)跟女同學(xué)聊天，而我在用手機(jī)看OI和ACM的題目。

自習(xí)課上我的那個(gè)朋友跟女同學(xué)一起學(xué)習(xí)，而我則翹課想去機(jī)房，有時(shí)候機(jī)房老師不讓我去，我就跑去天臺(tái)用草稿紙想題目。

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

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

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

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

努力沒有白費(fèi)，就像開了外掛一樣，陳立杰斬獲了國(guó)內(nèi)外信息競(jìng)賽多項(xiàng)大獎(jiǎng)：

2010年8月，全國(guó)信息學(xué)競(jìng)賽在線賽全場(chǎng)第2名。

2010年11月，全國(guó)信息學(xué)聯(lián)賽浙江賽區(qū)一等獎(jiǎng)。

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

2011年5月，中國(guó)隊(duì)選拔賽，非集訓(xùn)隊(duì)第2名。

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

2013年2月，全國(guó)信息學(xué)冬令營(yíng)全場(chǎng)第1名。

2013年7月，國(guó)際信息學(xué)奧林匹克競(jìng)賽第1名。

下圖左一為陳立杰

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

拿獎(jiǎng)拿到思考人生：這是我想要的生活嗎？

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

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

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

范浩強(qiáng)

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

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

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

后來，在唐平中教授指導(dǎo)下，陳立杰完成了第一篇學(xué)術(shù)論文，是基于圖靈機(jī)視角的對(duì)囚徒困境的探索，這篇論文成為了他探索科研的第一步。

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

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

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

后來的事實(shí)證明，陳立杰選擇的科研這條路走對(duì)了。

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

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

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

陳立杰大學(xué)成績(jī)單

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

“我想，對(duì)，我是陳立杰，我要成為一名理論計(jì)算機(jī)科學(xué)家！”

首位在計(jì)算機(jī)科學(xué)基礎(chǔ)年會(huì)上發(fā)文的中國(guó)本科生

興趣是最好的老師。

到了大三，陳立杰開始取得了一些“微小的成就”，他首次在理論計(jì)算機(jī)科學(xué)領(lǐng)域頂級(jí)的國(guó)際會(huì)議COLT 2016上發(fā)表文章，同時(shí)也提出了一個(gè)關(guān)于相關(guān)問題的猜想，并前往紐約會(huì)場(chǎng)做了兩篇口頭報(bào)告。

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

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

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

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

統(tǒng)計(jì)零知識(shí)證明原理

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

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

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

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

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

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

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

這之后，陳立杰又發(fā)表學(xué)術(shù)會(huì)議論文近10篇，并在多個(gè)學(xué)術(shù)研討會(huì)做過學(xué)術(shù)報(bào)告。

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

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

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

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

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

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

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

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

”我是陳立杰，我要成為一名理論計(jì)算機(jī)科學(xué)家！“