一個(gè)由3名中國(guó)本科生組成的團(tuán)隊(duì),，近日在全球頂會(huì)計(jì)算理論年會(huì)（STOC）上擊敗眾多本碩博組合,，摘得最佳學(xué)生論文獎(jiǎng)。

這項(xiàng)結(jié)果殊為不易,。其一,，STOC由美國(guó)計(jì)算機(jī)協(xié)會(huì)（ACM）舉辦，在理論計(jì)算機(jī)科學(xué)這座山峰上,，它是當(dāng)之無(wú)愧的峰頂會(huì)議,；其二，他們的論文從全球400多篇論文中突出重圍,，使其成為國(guó)內(nèi)本屆唯一獲此殊榮的團(tuán)隊(duì),；其三，這是中國(guó)在校大學(xué)生首次獲得該獎(jiǎng),。

3名學(xué)生都來(lái)自清華大學(xué)“姚班”,，分別是范致遠(yuǎn),、李嘉圖和楊天祺。

圖中分別為范致遠(yuǎn),、李嘉圖和楊天祺,。受訪者供圖

遙遙領(lǐng)先同齡人的3位00后學(xué)霸，并未因此太上頭,，“理論計(jì)算機(jī)科學(xué)研究猶如浩瀚大海,，我們所做的僅是冰山一角，是在打基礎(chǔ)而已,。將來(lái)還要付出更多的努力去解決計(jì)算復(fù)雜性領(lǐng)域的重要問(wèn)題,。”

優(yōu)中擇優(yōu)：獲獎(jiǎng)率僅約為2.9%

理論計(jì)算機(jī)科學(xué)領(lǐng)域有兩大頂會(huì),，一個(gè)是ACM（美國(guó)計(jì)算機(jī)學(xué)會(huì)）的STOC,，另外一個(gè)是IEEE（國(guó)際電氣和電子工程師協(xié)會(huì)）的FOCS。兩者都有著崇高的聲望,，而且是公認(rèn)難度最高的會(huì)議代表,。

今年全球投到STOC的論文共457篇，接收了135篇,，接收率約為29%,。

其中，評(píng)選出2篇最佳論文獎(jiǎng),，以及2篇最佳學(xué)生論文獎(jiǎng),，獲獎(jiǎng)率僅約為2.9%。最佳學(xué)生論文要求所有參與者都是博士學(xué)位以下的學(xué)生,，在全球范圍內(nèi)“優(yōu)中擇優(yōu)”,，競(jìng)爭(zhēng)非常激烈。即便是美國(guó)麻省理工學(xué)院,、普林斯頓大學(xué)等國(guó)際一流高校的本科生也很難“上榜”,。

獲得最佳論文獎(jiǎng)的2篇論文，分別來(lái)自魏茨曼科學(xué)研究所,、希伯來(lái)大學(xué),，以及莫斯科國(guó)立大學(xué)。圖片來(lái)源：STOC官網(wǎng)

最佳學(xué)生論文獎(jiǎng)的2篇論文,，分別來(lái)自微軟研究院,、麻省理工學(xué)院，以及清華大學(xué),。圖片來(lái)源：STOC官網(wǎng)

在高手云集的最高舞臺(tái)上,，范致遠(yuǎn)、李嘉圖與楊天祺共同完成的論文《偽隨機(jī)函數(shù)的精確復(fù)雜性與計(jì)算復(fù)雜性理論中自舉現(xiàn)象的黑盒自然證明障礙》突出重圍,，實(shí)屬不易,。

這篇論文的研究是開創(chuàng)性的,。論文研究了偽隨機(jī)函數(shù)的電路復(fù)雜性，在多個(gè)重要的電路復(fù)雜性類中對(duì)偽隨機(jī)函數(shù)給出了緊的上界與下界,。這些上下界結(jié)果為電路復(fù)雜性理論提供了新的理解,，也解釋了為何一些廣為相信的猜想難以被證明。

據(jù)《中國(guó)科學(xué)報(bào)》了解,，這三名同學(xué)并非從一開始就在一個(gè)團(tuán)隊(duì),。最初的思想雛形由李嘉圖和楊天祺提出。

在大一下學(xué)期,，世界著名計(jì)算機(jī)科學(xué)家,、中國(guó)科學(xué)院院士姚期智講授的計(jì)算機(jī)應(yīng)用數(shù)學(xué)課程，讓李嘉圖和楊天祺獲益匪淺,?！拔覀冋J(rèn)識(shí)到計(jì)算機(jī)科學(xué)是一個(gè)會(huì)產(chǎn)生許多有趣的、需要靈感和經(jīng)驗(yàn)才能解決的問(wèn)題的學(xué)科,?！?/span>

為了汲取更多關(guān)于計(jì)算機(jī)科學(xué)的知識(shí)，他們?cè)诖笠幌聦W(xué)期提前選修了段然老師的計(jì)算理論課程,。正是這門課程，使他們了解到計(jì)算復(fù)雜性這一領(lǐng)域有著許多懸而未決的困惑,，也有許多剛剛起步,、需要進(jìn)一步探索的課題方向。

兩人在課后查閱各種相關(guān)文獻(xiàn),，除了想彌補(bǔ)知識(shí)的不足,，也想找到目標(biāo)方向。那段時(shí)間,，他們一起翻看了近些年電路復(fù)雜性理論的一個(gè)重要突破,，即麻省理工學(xué)院教授Ryan Williams提出的，證明電路復(fù)雜度下界（circuit lower bound）的算法方法（algorithmic approach）,。

“我們想要從一個(gè)電路復(fù)雜度理論的前沿問(wèn)題入手,，了解這個(gè)領(lǐng)域的背景、主要技術(shù),，以及目前的重要問(wèn)題,。”李嘉圖表示,。

不過(guò),，實(shí)際進(jìn)展并不盡如人意。經(jīng)過(guò)一番學(xué)習(xí),，兩人雖然大致明白了這一方法的基本理論,，但并沒(méi)有找到可以進(jìn)一步探究的問(wèn)題,。

2021年春季學(xué)期，他們選修了陳一鐳老師講授的密碼學(xué)基礎(chǔ)課程后,，忽然感覺(jué)“柳暗花明”,。

“我倆在學(xué)習(xí)中想到，是否可以將密碼學(xué)與我們之前研究的電路復(fù)雜度問(wèn)題聯(lián)系起來(lái),，通過(guò)電路復(fù)雜度的技術(shù)研究構(gòu)建密碼系統(tǒng)所需計(jì)算資源的多少,，以完成課程要求的final project?！崩罴螆D說(shuō),。

所有選修該課程的同學(xué)都要以小組為單位，在課上作final project的報(bào)告,。恰好,，范致遠(yuǎn)也選修了這門課程，他在聽完李嘉圖和楊天祺的報(bào)告后,，主動(dòng)找到兩人,，并提出這個(gè)結(jié)果還可以有很大的改進(jìn)空間。

“在范致遠(yuǎn)加入之前,，我們當(dāng)時(shí)僅僅針對(duì)一個(gè)電路模型得到了復(fù)雜度下界,，結(jié)果較弱，技術(shù)也比較繁雜,，主要為后續(xù)研究指出了一個(gè)模糊的方向,。”楊天祺告訴《中國(guó)科學(xué)報(bào)》,。

范致遠(yuǎn)的出現(xiàn)猶如及時(shí)雨,，不僅提出改進(jìn)意見(jiàn)，還大大增加了李嘉圖和楊天祺對(duì)解決這一問(wèn)題的信心,。

“2+1”組合成團(tuán)后優(yōu)勢(shì)互補(bǔ),、實(shí)力大增。

“我們?nèi)齻€(gè)人的合作氛圍很舒服,，大家經(jīng)常交流和探討,，思想會(huì)碰撞出很多火花。后來(lái),，我們對(duì)原方法進(jìn)行了大幅度的簡(jiǎn)化和改進(jìn),，而且用完全不同的技術(shù)探索了這一問(wèn)題的更多側(cè)面?！狈吨逻h(yuǎn)說(shuō),。

相關(guān)研究有了質(zhì)的飛躍，以至于在最終的論文中,，原先預(yù)設(shè)的問(wèn)題甚至不再是最主要的結(jié)果,，而最后展示的結(jié)果也特別出彩——在三個(gè)模型中證明了上下界,。

姚班：“大神”聚集地

在這屆STOC接收的135篇論文里，有7篇出自姚班師生,。而在歷屆STOC接收的論文里,，也頻現(xiàn)姚班師生的身影，比如2020年就有4篇,，2021年有3篇,。

上一個(gè)獲STOC最佳學(xué)生論文獎(jiǎng)的中國(guó)人是陳立杰，他也是從姚班畢業(yè),。如今他在麻省理工學(xué)院深造,，上文中提到的Ryan Williams正是他的導(dǎo)師。

在許多姚班學(xué)生心里,，陳立杰是他們學(xué)習(xí)的榜樣,，是“bug”一樣的存在：他獲得2011年亞太地區(qū)信息學(xué)奧林匹克競(jìng)賽金牌，是2013年國(guó)際信息學(xué)奧林匹克競(jìng)賽第1名,，而且是國(guó)內(nèi)第一個(gè)在FOCS上發(fā)論文的本科生,，后來(lái)在2019年還拿到了FOCS最佳學(xué)生論文獎(jiǎng)，已然是理論計(jì)算機(jī)領(lǐng)域非常耀眼的新星,。

截至2021年12月,，姚班學(xué)生在本科期間發(fā)表的論文有358篇，作為論文通訊作者或主要完成人的有277篇,，并有121人次在FOCS,、STOC、SODA,、NIPS、COLT,、CVPR,、AAAI、ICLR等國(guó)際頂級(jí)會(huì)議上作大會(huì)報(bào)告,。

這不禁讓人好奇,，到底是一個(gè)怎樣的“神秘組織”，竟然能集結(jié)如此多的“大神”,？

姚班全稱是“清華學(xué)堂計(jì)算機(jī)科學(xué)實(shí)驗(yàn)班”,，隸屬于清華大學(xué)交叉信息研究院（以下簡(jiǎn)稱交叉信息院），由姚期智院士一手創(chuàng)辦,。

這個(gè)全球頂尖的精英班,，入選學(xué)生都非常優(yōu)秀。他們大多都是數(shù)學(xué)競(jìng)賽,、物理競(jìng)賽以及信息學(xué)競(jìng)賽的金牌獲得者,，

像范致遠(yuǎn),、李嘉圖和楊天祺，三人都是以保送方式進(jìn)入清華大學(xué),，再經(jīng)過(guò)層層選拔進(jìn)入姚班,。其中，范致遠(yuǎn)在第34屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽中拿到金牌,；李嘉圖和楊天祺在第35屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽中拿到金牌,。

在萬(wàn)里挑一的姚班，身邊都是清華里尖子生,，所有的核心課程都是全英文授課,，不做“拼命三郎”很容易落在后面。這里學(xué)術(shù)氛圍非常濃厚,，學(xué)生們互相切磋,，寢室里的每個(gè)角落都可能成為討論交流的地方。

范致遠(yuǎn),、李嘉圖和楊天祺都是理論基礎(chǔ)很強(qiáng),，且對(duì)學(xué)術(shù)研究很有興趣的學(xué)生，三人在姚班都十分刻苦,。他們認(rèn)為這次獲得最佳學(xué)生論文獎(jiǎng),，除了自身的努力，還離不開一位“大師”的支持和鼓勵(lì),。

“姚先生對(duì)我們的影響是巨大的,，他猶如我們前進(jìn)路上的燈塔?！?/span>楊天祺說(shuō),。

他和李嘉圖在前期大量閱讀國(guó)內(nèi)外論文時(shí)，也曾對(duì)所走之路感到迷茫,?！爱?dāng)時(shí)完全不知道從哪里下手，腦子里一堆知識(shí),，思維很混亂,。”

倆人鼓起勇氣主動(dòng)找姚期智院士談心,?！耙ο壬鷮?duì)我們通過(guò)閱讀論文學(xué)習(xí)的方法表示贊賞，也指出作為新手想要從前沿論文中直接找到可以下手的問(wèn)題確實(shí)非常困難,?！?/p>

“另一方面，姚先生認(rèn)為我們靠之前的學(xué)習(xí)已經(jīng)有了一定的知識(shí)儲(chǔ)備，應(yīng)當(dāng)上手嘗試解決一些問(wèn)題,，積累做研究的經(jīng)驗(yàn),。”李嘉圖說(shuō),，“因此,，他建議我們研究'顯式復(fù)雜度下界’這一問(wèn)題?！?/p>

該建議立馬讓倆人眼前一亮,。要知道，這個(gè)問(wèn)題非常有名,，是電路復(fù)雜度這一領(lǐng)域最早也是最根本的問(wèn)題,。

不僅如此，它還是該領(lǐng)域令人抓狂的難題,。從上世紀(jì)50年代到現(xiàn)在,，關(guān)于這個(gè)問(wèn)題還沒(méi)有任何根本性的進(jìn)展，并且許多對(duì)已有結(jié)果的改進(jìn)都非常繁雜,。該問(wèn)題上一次被改進(jìn)是2016年,，再上一次則要追溯到上世紀(jì)80年代。

往往越復(fù)雜的問(wèn)題,，處理的辦法越簡(jiǎn)單,。正因?yàn)閷?duì)這一問(wèn)題人們沒(méi)有根本性的新認(rèn)識(shí)，所以對(duì)已有結(jié)果的改進(jìn)或許并不依賴于復(fù)雜的技術(shù),，可能更需要的是簡(jiǎn)單的靈感和細(xì)致的分類討論,。

“也就是說(shuō)，不需要太多背景知識(shí),。這對(duì)我們這樣的新手來(lái)說(shuō)非常適合,。”楊天祺表示,。

值得一提的是,，李嘉圖和楊天祺對(duì)該問(wèn)題的研究形成的論文，也被這屆STOC接收了,。這為他們?cè)陔娐窂?fù)雜度這一領(lǐng)域積累了經(jīng)驗(yàn)，也是完成這篇最佳學(xué)生論文的一個(gè)相當(dāng)重要的基礎(chǔ),。

李嘉圖和楊天祺合作的論文,，被STOC 2022接收。圖片來(lái)源：清華大學(xué)交叉信息研究院

“姚先生對(duì)我們的結(jié)果很滿意,。他是獲得圖靈獎(jiǎng)的唯一華人,，圖靈獎(jiǎng)是計(jì)算機(jī)界的諾貝爾獎(jiǎng)，獲得他的認(rèn)可，給予了我們相當(dāng)大的信心,，也堅(jiān)定了未來(lái)想繼續(xù)從事科研工作的決心,。”楊天祺說(shuō),。

他引用了偶像師兄陳立杰在2016清華特等獎(jiǎng)答辯現(xiàn)場(chǎng)說(shuō)的那句話,，來(lái)抒發(fā)心中抱負(fù)。

“姚先生曾說(shuō),，現(xiàn)在是計(jì)算機(jī)科學(xué)的黃金時(shí)代,，也是全人類的黃金時(shí)代！出生在這樣一個(gè)黃金時(shí)代里,，我感到無(wú)比榮幸,，我夢(mèng)想能成為黃金時(shí)代浪潮中的一朵浪花，為人類的智慧添磚加瓦,！”