【新智元導讀】

理論計算機科學領域最頂級的國際會議 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 上發表文章，同時也提出了一個關於相關問題的猜想，並前往紐約會場做了兩篇口頭報告。

陳立傑在 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）接收，陳立傑也成為

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

。

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

到大四畢業前，陳立傑就已經在國際會議上發表了四篇學術論文，一篇文章還獲得 ISAAC 會議最佳學生論文獎。

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

這之後，陳立傑又發表學術會議論文近 10 篇，並在多個學術研討會做過學術報告。

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

他說，在姚班，已經有三十三個同學發表了二十三篇 paper！

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

陳立傑：

對，是這樣子的！（掌聲）

評委：

你有想法了嗎？現在為了解決這個問題提了很多方案，你有想法了嗎？

陳立傑：

是這樣子的，這個問題已經困擾了計算機學界，可以說是從計算機這個領域一開始以來就有的問題。我現在作為一個大四的學生，可能確實暫時還沒什麼想法，但我相信隨著我的知識的拓展，

在我有生之年我能夠看到這個問題的解決

。（掌聲）

陳立傑在2016清華特等獎答辯現場

https：//www。zhihu。com/video/1092786315136933888

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

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

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

參考資料：

新智元 · AI_era

每日推送 AI 領域前沿學術解讀、AI 產業最新資訊

戳右上角【+ 關注】↗↗

喜歡請分享、點贊吧