?
                     
                    作者:張晴丹 來源:科學網微信公號 發布時間:2022/6/22 20:07:58
                    選擇字號:
                    國內首次!清華姚班本科生斬獲全球理論計算機頂會大獎

                     

                    一個由3名中國本科生組成的團隊,近日在全球頂會計算理論年會(STOC)上擊敗眾多本碩博組合,摘得最佳學生論文獎。

                    這項結果殊為不易。其一,STOC由美國計算機協會(ACM)舉辦,在理論計算機科學這座山峰上,它是當之無愧的峰頂會議;其二,他們的論文從全球400多篇論文中突出重圍,使其成為國內本屆唯一獲此殊榮的團隊;其三,這是中國在校大學生首次獲得該獎。

                    3名學生都來自清華大學“姚班”,分別是范致遠、李嘉圖和楊天祺。他們即將在6月23日參加STOC 2022 ,“我們正在抓緊時間準備STOC的演講視頻!”

                    圖中分別為范致遠、李嘉圖和楊天祺。受訪者供圖

                    遙遙領先同齡人的3位00后學霸,并未因此太上頭,“理論計算機科學研究猶如浩瀚大海,我們所做的僅是冰山一角,是在打基礎而已。將來還要付出更多的努力去解決計算復雜性領域的重要問題。”

                    優中擇優:獲獎率僅約為2.9%

                    理論計算機科學領域有兩大頂會,一個是ACM(美國計算機學會)的STOC,另外一個是IEEE(國際電氣和電子工程師協會)的FOCS。兩者都有著崇高的聲望,而且是公認難度最高的會議代表。

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

                    其中,評選出2篇最佳論文獎,以及2篇最佳學生論文獎,獲獎率僅約為2.9%。最佳學生論文要求所有參與者都是博士學位以下的學生,在全球范圍內“優中擇優”,競爭非常激烈。即便是美國麻省理工學院、普林斯頓大學等國際一流高校的本科生也很難“上榜”。

                    獲得最佳論文獎的2篇論文,分別來自魏茨曼科學研究所、希伯來大學,以及莫斯科國立大學。圖片來源:STOC官網

                     

                    最佳學生論文獎的2篇論文,分別來自微軟研究院、麻省理工學院,以及清華大學。圖片來源:STOC官網

                    在高手云集的最高舞臺上,范致遠、李嘉圖與楊天祺共同完成的論文《偽隨機函數的精確復雜性與計算復雜性理論中自舉現象的黑盒自然證明障礙》突出重圍,實屬不易。

                    這篇論文的研究是開創性的。論文研究了偽隨機函數的電路復雜性,在多個重要的電路復雜性類中對偽隨機函數給出了緊的上界與下界。這些上下界結果為電路復雜性理論提供了新的理解,也解釋了為何一些廣為相信的猜想難以被證明。

                    據《中國科學報》了解,這三名同學并非從一開始就在一個團隊。最初的思想雛形由李嘉圖和楊天祺提出。

                    在大一下學期,世界著名計算機科學家、中國科學院院士姚期智講授的計算機應用數學課程,讓李嘉圖和楊天祺獲益匪淺。“我們認識到計算機科學是一個會產生許多有趣的、需要靈感和經驗才能解決的問題的學科。”

                    為了汲取更多關于計算機科學的知識,他們在大一下學期提前選修段然老師的計算理論課程。正是這門課程,使他們了解到計算復雜性這一領域有著許多懸而未決的難題,也有許多剛剛起步、需要進一步探索的方向。

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

                    “我們想要從一個電路復雜度理論的前沿問題入手,了解這個領域的背景、主要技術,以及目前的重要問題。”李嘉圖在接受《中國科學報》采訪時表示。

                    不過,實際進展并不盡如人意。經過一番學習,兩人雖然大致明白了這一方法的基本理論,但并沒有找到可以進一步探究的問題。

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

                    “我倆在學習中想到,是否可以將密碼學與我們之前研究的電路復雜度問題聯系起來,通過電路復雜度的技術研究構建密碼系統所需計算資源的多少,以完成課程要求的final project。”李嘉圖說。

                    所有選修該課程的同學都要以小組為單位,在課上作final project的報告。恰好,范致遠也選修了這門課程,他在聽完李嘉圖和楊天祺的報告后,主動找到兩人,并提出這個結果還可以有很大的改進空間。

                    “在范致遠加入之前,我們當時僅僅針對一個電路模型得到了復雜度下界,結果較弱,技術也比較繁雜,主要為后續研究指出了一個模糊的方向。”楊天祺告訴《中國科學報》。

                    范致遠的出現猶如及時雨,不僅提出改進意見,還大大增加了李嘉圖和楊天祺對解決這一問題的信心。

                    “2+1”組合成團后優勢互補、實力大增。

                    “我們三個人的合作氛圍很舒服,大家經常交流和探討,思想會碰撞出很多火花。后來,我們對原方法進行了大幅度的簡化和改進,而且用完全不同的技術探索了這一問題的更多側面。”范致遠告訴《中國科學報》。

                    相關研究有了質的飛躍,以至于在最終的論文中,原先預設的問題甚至不再是最主要的結果,而最后展示的結果也特別出彩——在三個模型中證明了上下界。

                    姚班:“大神”聚集地

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

                    上一個獲STOC最佳學生論文獎的中國人是陳立杰,他也是從姚班畢業。如今他在麻省理工學院深造,上文中提到的Ryan Williams正是他的導師。

                    在許多姚班學生心里,陳立杰是他們學習的榜樣,是“bug”一樣的存在:他獲得2011年亞太地區信息學奧林匹克競賽金牌,是2013年國際信息學奧林匹克競賽第1名,而且是國內第一個在FOCS上發論文的本科生,后來在2019年還拿到了FOCS最佳學生論文獎,已然是理論計算機領域非常耀眼的新星。

                    可以說,姚班對計算機科學領域貢獻巨大。

                    截至2021年12月,姚班學生在本科期間發表的論文有358篇,作為論文通訊作者或主要完成人的有277篇,并有121人次在FOCS、STOC、SODA、NIPS、COLT、CVPR、AAAI、ICLR等國際頂級會議上作大會報告。

                    這不禁讓人好奇,到底是一個怎樣的“神秘組織”,竟然能集結如此多的“大神”?

                    姚班全稱是“清華學堂計算機科學實驗班”,隸屬于清華大學交叉信息研究院(以下簡稱交叉信息院),由姚期智院士一手創辦。

                    這個全球最頂尖的精英班,入選學生都是學霸中的學霸。他們大多都是數學競賽、物理競賽以及信息學競賽的金牌獲得者,或者各省高考狀元等,多以保送或自主招生的方式加入姚班。

                    像范致遠、李嘉圖和楊天祺,三人都是以保送方式進入清華大學,再經過層層選拔進入姚班。其中,范致遠在第34屆全國青少年信息學奧林匹克競賽中拿到金牌;李嘉圖和楊天祺在第35屆全國青少年信息學奧林匹克競賽中拿到金牌。

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

                    范致遠、李嘉圖和楊天祺都是理論基礎很強,且對學術研究很有興趣,三人在姚班都十分刻苦。他們認為這次獲得最佳學生論文獎,除了自身的努力,還離不開一位“大師”的支持和鼓勵。

                    “姚先生對我們的影響是巨大的,他猶如我們前進路上的燈塔。”楊天祺說。

                    他和李嘉圖在前期大量閱讀國內外論文時,也曾對所走之路感到迷茫。“當時完全不知道從哪里下手,腦子里一堆知識,思維很混亂。”

                    倆人鼓起勇氣主動找姚期智院士談心。“姚先生對我們通過閱讀論文學習的方法表示贊賞,也指出作為新手想要從前沿論文中直接找到可以下手的問題確實非常困難。”

                    “另一方面,姚先生認為我們靠之前的學習已經有了一定的知識儲備,應當上手嘗試解決一些問題,積累做研究的經驗。”李嘉圖說,“因此,他建議我們研究‘顯式復雜度下界’這一問題。”

                    該建議立馬讓倆人眼前一亮。要知道,這個問題非常有名,是電路復雜度這一領域最早也是最根本的問題。

                    不僅如此,它還是該領域令人抓狂的難題。從上世紀50年代到現在,關于這個問題還沒有任何根本性的進展,并且許多對已有結果的改進都非常繁雜。該問題上一次被改進是2016年,再上一次則要追溯到上世紀80年代。

                    往往越復雜的問題,處理的辦法越簡單。正因為對這一問題人們沒有根本性的新認識,所以對已有結果的改進或許并不依賴于復雜的技術,可能更需要的是簡單的靈感和細致的分類討論。

                    “也就是說,不需要太多背景知識。這對我們這樣的新手來說非常適合。”楊天祺表示。

                    值得一提的是,李嘉圖和楊天祺對該問題的研究形成的論文,也被這屆STOC接收了。這為他們在電路復雜度這一領域積累了經驗,也是完成這篇最佳學生論文的一個相當重要的基礎。

                    李嘉圖和楊天祺合作的論文,被STOC 2022接收。圖片來源:清華大學交叉信息研究院

                    “姚先生對我們的結果很滿意。他是獲得圖靈獎的唯一華人,圖靈獎是計算機界的諾貝爾獎,能獲得他的認可,給了我們相當大的信心,也堅定了未來想繼續從事科研工作的決心。”楊天祺說。

                    他引用了偶像師兄陳立杰在2016清華特等獎答辯現場說的那句話,來抒發心中抱負。

                    “姚先生曾說,現在是計算機科學的黃金時代,也是全人類的黃金時代!出生在這樣一個黃金時代里,我感到無比榮幸,我夢想能成為黃金時代浪潮中的一朵浪花,為人類的智慧添磚加瓦!”

                    論文鏈接:

                    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

                     
                    特別聲明:本文轉載僅僅是出于傳播信息的需要,并不意味著代表本網站觀點或證實其內容的真實性;如其他媒體、網站或個人從本網站轉載使用,須保留本網站注明的“來源”,并自負版權等法律責任;作者如果不希望被轉載或者聯系轉載稿費等事宜,請與我們接洽。
                     
                     打印  發E-mail給: 
                        
                     
                    相關新聞 相關論文
                    ?
                    圖片新聞
                    30厘米!問天實驗艙水稻長勢喜人 翼龍成功實施四川高溫抗旱人工影響天氣
                    利用3D打印技術制造柔性電致發光裝置 早期人類700萬年前或直立行走
                    >>更多
                     
                    一周新聞排行
                     
                    編輯部推薦博文
                     
                    av色导航