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