一個由3名中國本科生組成的團(tuán)隊(duì)，近日在全球頂會計(jì)算理論年會（STOC）上擊敗眾多本碩博組合，摘得最佳學(xué)生論文獎。
(資料圖)
這項(xiàng)結(jié)果殊為不易。其一，STOC由美國計(jì)算機(jī)協(xié)會（ACM）舉辦，在理論計(jì)算機(jī)科學(xué)這座山峰上，它是當(dāng)之無愧的峰頂會議；其二，他們的論文從全球400多篇論文中突出重圍，使其成為國內(nèi)本屆唯一獲此殊榮的團(tuán)隊(duì)；其三，這是中國在校大學(xué)生首次獲得該獎。
3名學(xué)生都來自清華大學(xué)“姚班”，分別是范致遠(yuǎn)、李嘉圖和楊天祺。他們即將在6月23日參加STOC 2022 ，“我們正在抓緊時間準(zhǔn)備STOC的演講視頻！”
圖中分別為范致遠(yuǎn)、李嘉圖和楊天祺。受訪者供圖
遙遙領(lǐng)先同齡人的3位00后學(xué)霸，并未因此太上頭，“理論計(jì)算機(jī)科學(xué)研究猶如浩瀚大海，我們所做的僅是冰山一角，是在打基礎(chǔ)而已。將來還要付出更多的努力去解決計(jì)算復(fù)雜性領(lǐng)域的重要問題。”
優(yōu)中擇優(yōu)：獲獎率僅約為2.9%
理論計(jì)算機(jī)科學(xué)領(lǐng)域有兩大頂會，一個是ACM（美國計(jì)算機(jī)學(xué)會）的STOC，另外一個是IEEE（國際電氣和電子工程師協(xié)會）的FOCS。兩者都有著崇高的聲望，而且是公認(rèn)難度最高的會議代表。
今年全球投到STOC的論文共457篇，接收了135篇，接收率約為29%。
其中，評選出2篇最佳論文獎，以及2篇最佳學(xué)生論文獎，獲獎率僅約為2.9%。最佳學(xué)生論文要求所有參與者都是博士學(xué)位以下的學(xué)生，在全球范圍內(nèi)“優(yōu)中擇優(yōu)”，競爭非常激烈。即便是美國麻省理工學(xué)院、普林斯頓大學(xué)等國際一流高校的本科生也很難“上榜”。
獲得最佳論文獎的2篇論文，分別來自魏茨曼科學(xué)研究所、希伯來大學(xué)，以及莫斯科國立大學(xué)。圖片來源：STOC官網(wǎng)
最佳學(xué)生論文獎的2篇論文，分別來自微軟研究院、麻省理工學(xué)院，以及清華大學(xué)。圖片來源：STOC官網(wǎng)
在高手云集的最高舞臺上，范致遠(yuǎn)、李嘉圖與楊天祺共同完成的論文《偽隨機(jī)函數(shù)的精確復(fù)雜性與計(jì)算復(fù)雜性理論中自舉現(xiàn)象的黑盒自然證明障礙》突出重圍，實(shí)屬不易。
這篇論文的研究是開創(chuàng)性的。論文研究了偽隨機(jī)函數(shù)的電路復(fù)雜性，在多個重要的電路復(fù)雜性類中對偽隨機(jī)函數(shù)給出了緊的上界與下界。這些上下界結(jié)果為電路復(fù)雜性理論提供了新的理解，也解釋了為何一些廣為相信的猜想難以被證明。
據(jù)《中國科學(xué)報》了解，這三名同學(xué)并非從一開始就在一個團(tuán)隊(duì)。最初的思想雛形由李嘉圖和楊天祺提出。
在大一下學(xué)期，世界著名計(jì)算機(jī)科學(xué)家、中國科學(xué)院院士姚期智講授的計(jì)算機(jī)應(yīng)用數(shù)學(xué)課程，讓李嘉圖和楊天祺獲益匪淺。“我們認(rèn)識到計(jì)算機(jī)科學(xué)是一個會產(chǎn)生許多有趣的、需要靈感和經(jīng)驗(yàn)才能解決的問題的學(xué)科。”
為了汲取更多關(guān)于計(jì)算機(jī)科學(xué)的知識，他們在大一下學(xué)期提前選修段然老師的計(jì)算理論課程。正是這門課程，使他們了解到計(jì)算復(fù)雜性這一領(lǐng)域有著許多懸而未決的難題，也有許多剛剛起步、需要進(jìn)一步探索的方向。
兩人在課后查閱各種相關(guān)文獻(xiàn)，除了想彌補(bǔ)知識的不足，也想找到目標(biāo)方向。那段時間，他們一起翻看了近些年電路復(fù)雜性理論的一個重要突破，即麻省理工學(xué)院教授Ryan Williams提出的，證明電路復(fù)雜度下界（circuit lower bound）的算法方法（algorithmic approach）。
“我們想要從一個電路復(fù)雜度理論的前沿問題入手，了解這個領(lǐng)域的背景、主要技術(shù)，以及目前的重要問題。”李嘉圖在接受《中國科學(xué)報》采訪時表示。
不過，實(shí)際進(jìn)展并不盡如人意。經(jīng)過一番學(xué)習(xí)，兩人雖然大致明白了這一方法的基本理論，但并沒有找到可以進(jìn)一步探究的問題。
2021年春季學(xué)期，他們選修了陳一鐳老師講授的密碼學(xué)基礎(chǔ)課程后，忽然感覺“柳暗花明”。
“我倆在學(xué)習(xí)中想到，是否可以將密碼學(xué)與我們之前研究的電路復(fù)雜度問題聯(lián)系起來，通過電路復(fù)雜度的技術(shù)研究構(gòu)建密碼系統(tǒng)所需計(jì)算資源的多少，以完成課程要求的final project。”李嘉圖說。
所有選修該課程的同學(xué)都要以小組為單位，在課上作final project的報告。恰好，范致遠(yuǎn)也選修了這門課程，他在聽完李嘉圖和楊天祺的報告后，主動找到兩人，并提出這個結(jié)果還可以有很大的改進(jìn)空間。
“在范致遠(yuǎn)加入之前，我們當(dāng)時僅僅針對一個電路模型得到了復(fù)雜度下界，結(jié)果較弱，技術(shù)也比較繁雜，主要為后續(xù)研究指出了一個模糊的方向。”楊天祺告訴《中國科學(xué)報》。
范致遠(yuǎn)的出現(xiàn)猶如及時雨，不僅提出改進(jìn)意見，還大大增加了李嘉圖和楊天祺對解決這一問題的信心。
“2+1”組合成團(tuán)后優(yōu)勢互補(bǔ)、實(shí)力大增。
“我們?nèi)齻€人的合作氛圍很舒服，大家經(jīng)常交流和探討，思想會碰撞出很多火花。后來，我們對原方法進(jìn)行了大幅度的簡化和改進(jìn)，而且用完全不同的技術(shù)探索了這一問題的更多側(cè)面。”范致遠(yuǎn)告訴《中國科學(xué)報》。
相關(guān)研究有了質(zhì)的飛躍，以至于在最終的論文中，原先預(yù)設(shè)的問題甚至不再是最主要的結(jié)果，而最后展示的結(jié)果也特別出彩——在三個模型中證明了上下界。
姚班：“大神”聚集地
在這屆STOC接收的135篇論文里，有7篇出自姚班師生。而在歷屆STOC接收的論文里，也頻現(xiàn)姚班師生的身影，比如2020年就有4篇，2021年有3篇。
上一個獲STOC最佳學(xué)生論文獎的中國人是陳立杰，他也是從姚班畢業(yè)。如今他在麻省理工學(xué)院深造，上文中提到的Ryan Williams正是他的導(dǎo)師。
在許多姚班學(xué)生心里，陳立杰是他們學(xué)習(xí)的榜樣，是“bug”一樣的存在：他獲得2011年亞太地區(qū)信息學(xué)奧林匹克競賽金牌，是2013年國際信息學(xué)奧林匹克競賽第1名，而且是國內(nèi)第一個在FOCS上發(fā)論文的本科生，后來在2019年還拿到了FOCS最佳學(xué)生論文獎，已然是理論計(jì)算機(jī)領(lǐng)域非常耀眼的新星。
可以說，姚班對計(jì)算機(jī)科學(xué)領(lǐng)域貢獻(xiàn)巨大。
截至2021年12月，姚班學(xué)生在本科期間發(fā)表的論文有358篇，作為論文通訊作者或主要完成人的有277篇，并有121人次在FOCS、STOC、SODA、NIPS、COLT、CVPR、AAAI、ICLR等國際頂級會議上作大會報告。
這不禁讓人好奇，到底是一個怎樣的“神秘組織”，竟然能集結(jié)如此多的“大神”？
姚班全稱是“清華學(xué)堂計(jì)算機(jī)科學(xué)實(shí)驗(yàn)班”，隸屬于清華大學(xué)交叉信息研究院（以下簡稱交叉信息院），由姚期智院士一手創(chuàng)辦。
這個全球最頂尖的精英班，入選學(xué)生都是學(xué)霸中的學(xué)霸。他們大多都是數(shù)學(xué)競賽、物理競賽以及信息學(xué)競賽的金牌獲得者，或者各省高考狀元等，多以保送或自主招生的方式加入姚班。
像范致遠(yuǎn)、李嘉圖和楊天祺，三人都是以保送方式進(jìn)入清華大學(xué)，再經(jīng)過層層選拔進(jìn)入姚班。其中，范致遠(yuǎn)在第34屆全國青少年信息學(xué)奧林匹克競賽中拿到金牌；李嘉圖和楊天祺在第35屆全國青少年信息學(xué)奧林匹克競賽中拿到金牌。
在萬里挑一的姚班，身邊都是清華里尖子生，所有的核心課程都是全英文授課，不做“拼命三郎”很容易落在后面。這里學(xué)術(shù)氛圍非常濃厚，學(xué)生們互相切磋，寢室里的每個角落都可能成為討論交流的地方。
范致遠(yuǎn)、李嘉圖和楊天祺都是理論基礎(chǔ)很強(qiáng)，且對學(xué)術(shù)研究很有興趣，三人在姚班都十分刻苦。他們認(rèn)為這次獲得最佳學(xué)生論文獎，除了自身的努力，還離不開一位“大師”的支持和鼓勵。
“姚先生對我們的影響是巨大的，他猶如我們前進(jìn)路上的燈塔。”楊天祺說。
他和李嘉圖在前期大量閱讀國內(nèi)外論文時，也曾對所走之路感到迷茫。“當(dāng)時完全不知道從哪里下手，腦子里一堆知識，思維很混亂。”
倆人鼓起勇氣主動找姚期智院士談心。“姚先生對我們通過閱讀論文學(xué)習(xí)的方法表示贊賞，也指出作為新手想要從前沿論文中直接找到可以下手的問題確實(shí)非常困難。”
“另一方面，姚先生認(rèn)為我們靠之前的學(xué)習(xí)已經(jīng)有了一定的知識儲備，應(yīng)當(dāng)上手嘗試解決一些問題，積累做研究的經(jīng)驗(yàn)。”李嘉圖說，“因此，他建議我們研究‘顯式復(fù)雜度下界’這一問題。”
該建議立馬讓倆人眼前一亮。要知道，這個問題非常有名，是電路復(fù)雜度這一領(lǐng)域最早也是最根本的問題。
不僅如此，它還是該領(lǐng)域令人抓狂的難題。從上世紀(jì)50年代到現(xiàn)在，關(guān)于這個問題還沒有任何根本性的進(jìn)展，并且許多對已有結(jié)果的改進(jìn)都非常繁雜。該問題上一次被改進(jìn)是2016年，再上一次則要追溯到上世紀(jì)80年代。
往往越復(fù)雜的問題，處理的辦法越簡單。正因?yàn)閷@一問題人們沒有根本性的新認(rèn)識，所以對已有結(jié)果的改進(jìn)或許并不依賴于復(fù)雜的技術(shù)，可能更需要的是簡單的靈感和細(xì)致的分類討論。
“也就是說，不需要太多背景知識。這對我們這樣的新手來說非常適合。”楊天祺表示。
值得一提的是，李嘉圖和楊天祺對該問題的研究形成的論文，也被這屆STOC接收了。這為他們在電路復(fù)雜度這一領(lǐng)域積累了經(jīng)驗(yàn)，也是完成這篇最佳學(xué)生論文的一個相當(dāng)重要的基礎(chǔ)。
李嘉圖和楊天祺合作的論文，被STOC 2022接收。圖片來源：清華大學(xué)交叉信息研究院
“姚先生對我們的結(jié)果很滿意。他是獲得圖靈獎的唯一華人，圖靈獎是計(jì)算機(jī)界的諾貝爾獎，能獲得他的認(rèn)可，給了我們相當(dāng)大的信心，也堅(jiān)定了未來想繼續(xù)從事科研工作的決心。”楊天祺說。
他引用了偶像師兄陳立杰在2016清華特等獎答辯現(xiàn)場說的那句話，來抒發(fā)心中抱負(fù)。
“姚先生曾說，現(xiàn)在是計(jì)算機(jī)科學(xué)的黃金時代，也是全人類的黃金時代！出生在這樣一個黃金時代里，我感到無比榮幸，我夢想能成為黃金時代浪潮中的一朵浪花，為人類的智慧添磚加瓦！”
論文鏈接：
https://eccc.weizmann.ac.il/report/2021/125/
https://eccc.weizmann.ac.il/report/2021/023/
參考鏈接：
https://www.tsinghua.edu.cn/info/1175/94548.htm
https://iiis.tsinghua.edu.cn/index.php?v=show&cid=623&id=5804
https://mp.weixin.qq.com/s/zlw7i-QmCZBH8qpoMLR8_Q
https://zhuanlan.zhihu.com/p/60156478?utm_source=wechat_session&utm_medium=social&utm_oi=685086348583505920
https://mp.weixin.qq.com/s/Q3wRcZCiuFk_0f_FcNmc8w
標(biāo)簽：
