一個(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)、李嘉圖和楊天祺。他們即將在6月23日參加STOC 2022 ，“我們正在抓緊時(shí)間準(zhǔn)備STOC的演講視頻！”
圖中分別為范致遠(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í)屬不易。
這篇論文的研究是開(kāi)創(chuàng)性的。論文研究了偽隨機(jī)函數(shù)的電路復(fù)雜性，在多個(gè)重要的電路復(fù)雜性類中對(duì)偽隨機(jī)函數(shù)給出了緊的上界與下界。這些上下界結(jié)果為電路復(fù)雜性理論提供了新的理解，也解釋了為何一些廣為相信的猜想難以被證明。
據(jù)《中國(guó)科學(xué)報(bào)》了解，這三名同學(xué)并非從一開(kāi)始就在一個(gè)團(tuán)隊(duì)。最初的思想雛形由李嘉圖和楊天祺提出。
在大一下學(xué)期，世界著名計(jì)算機(jī)科學(xué)家、中國(guó)科學(xué)院院士姚期智講授的計(jì)算機(jī)應(yīng)用數(shù)學(xué)課程，讓李嘉圖和楊天祺獲益匪淺。“我們認(rèn)識(shí)到計(jì)算機(jī)科學(xué)是一個(gè)會(huì)產(chǎn)生許多有趣的、需要靈感和經(jīng)驗(yàn)才能解決的問(wèn)題的學(xué)科。”
為了汲取更多關(guān)于計(jì)算機(jī)科學(xué)的知識(shí)，他們?cè)诖笠幌聦W(xué)期提前選修段然老師的計(jì)算理論課程。正是這門(mén)課程，使他們了解到計(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ó)科學(xué)報(bào)》采訪時(shí)表示。
不過(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。”李嘉圖說(shuō)。
所有選修該課程的同學(xué)都要以小組為單位，在課上作final project的報(bào)告。恰好，范致遠(yuǎn)也選修了這門(mén)課程，他在聽(tīng)完李嘉圖和楊天祺的報(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è)面。”范致遠(yuǎn)告訴《中國(guó)科學(xué)報(bào)》。
相關(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)域非常耀眼的新星。
可以說(shuō)，姚班對(duì)計(jì)算機(jī)科學(xué)領(lǐng)域貢獻(xiàn)巨大。
截至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é)生都是學(xué)霸中的學(xué)霸。他們大多都是數(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ù)研究很有興趣，三人在姚班都十分刻苦。他們認(rèn)為這次獲得最佳學(xué)生論文獎(jiǎng)，除了自身的努力，還離不開(kāi)一位“大師”的支持和鼓勵(lì)。
“姚先生對(duì)我們的影響是巨大的，他猶如我們前進(jìn)路上的燈塔。”楊天祺說(shuō)。
他和李嘉圖在前期大量閱讀國(guó)內(nèi)外論文時(shí)，也曾對(duì)所走之路感到迷茫。“當(dāng)時(shí)完全不知道從哪里下手，腦子里一堆知識(shí)，思維很混亂。”
倆人鼓起勇氣主動(dòng)找姚期智院士談心。“姚先生對(duì)我們通過(guò)閱讀論文學(xué)習(xí)的方法表示贊賞，也指出作為新手想要從前沿論文中直接找到可以下手的問(wèn)題確實(shí)非常困難。”
“另一方面，姚先生認(rèn)為我們靠之前的學(xué)習(xí)已經(jīng)有了一定的知識(shí)儲(chǔ)備，應(yīng)當(dāng)上手嘗試解決一些問(wèn)題，積累做研究的經(jīng)驗(yàn)。”李嘉圖說(shuō)，“因此，他建議我們研究‘顯式復(fù)雜度下界’這一問(wèn)題。”
該建議立馬讓倆人眼前一亮。要知道，這個(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í)代浪潮中的一朵浪花，為人類的智慧添磚加瓦！”
論文鏈接：
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)簽：
