95后的理論計算機(jī)科學(xué)家來了！我是陳立杰，我要成為一名理論計算機(jī)科學(xué)家！

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

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

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

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

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

陳立杰

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

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

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

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

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

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

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

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

2013全國信息學(xué)冬令營全場第1名；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

下圖左一為陳立杰

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

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

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

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

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

范浩強

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

興趣是最好的老師。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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