姚期智施堯耘獲FOCS 2021時間檢驗獎，MIT華人學霸毛嘯摘最佳學生論文獎
計算機理論頂會FOCS論文獎項頒出
魚羊 發(fā)自 凹非寺
量子位 報道 | 公眾號 QbitAI
計算機理論頂會FOCS 2021各項論文獎項已公布。
最佳學生論文獎被MIT華人學霸毛嘯收入囊中。
而姚期智院士和達摩院量子實驗室負責人施堯耘則憑借2001年發(fā)表的論文《Informationl Complexity and the Direct Sum Problem for Simultaneous Message Complexity》，獲得時間檢驗獎。
另外，最佳論文獎由來自印度理工學院、丹麥奧胡斯大學等多家研究機構(gòu)的國際團隊獲得。
作為中國計算機學會（CCF）推薦的計算機科學理論方向A類會議，F(xiàn)OCS這樣的頂會被公認為是計算機科學領域難度最大、含金量最高的會議。
FOCS 2021將于2022年2月7日-10日在美國科羅拉多州丹佛市舉辦。
論文詳情，我們具體來看。
最佳學生論文獎：打破未加權(quán)樹編輯距離問題三次障礙
n節(jié)點樹的（非加權(quán)）樹編輯距離問題要求計算兩個帶節(jié)點標簽的有根樹之間的相似度。
目前的最佳算法時間復雜度為O（n3）。同一篇論文還表明，O（n3）是任何使用了所謂分解策略的算法的最佳運行時間。
根據(jù)APSP猜想，該問題無法在亞立方時間內(nèi)解決。
但本文作者用一種時間復雜度為O（n2.9546）的算法解決了未加權(quán)的樹編輯距離問題，打破了三次障礙。
作者考慮了一個等價的最大化問題，并使用了一種設計具有許多特殊屬性的矩陣的動態(tài)編程方案。通過使用分解方案以及一些組合技術(shù)，將樹編輯距離減少到有界差分矩陣的最大加乘積，真正在亞立方時間內(nèi)解決問題。
論文作者毛嘯曾就讀于長沙雅禮中學，是2017年國際奧林匹克信息學競賽（IOI）銀牌得主。
他高中畢業(yè)時，在MIT全獎和清華保送之間，選擇了到MIT攻讀計算機科學和數(shù)學相關(guān)專業(yè)。
今年，他剛剛本科畢業(yè)，現(xiàn)為MIT工程學碩士。
此前，他的MIT校友、姚班畢業(yè)生陳立杰也曾獲FOCS 2019最佳學生論文獎。
姚期智、施堯耘2001年論文獲時間檢驗獎
姚期智院士此番憑借他和Amit Chakrabarti、施堯耘、Anthony Wirth合著的《Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity》獲頒FOCS 2021時間檢驗獎。
這篇論文探討的是同步消息復雜度的直和問題，并引入了新的信息復雜度概念。
給定同一個問題的m個副本，是否需要m倍的資源才能解決這m個問題？這就是直和問題。這篇論文在姚期智提出的同步消息（SM）傳播模型中研究了這個問題。
這是FOCS第三次頒出時間檢驗獎。頒獎對象是1991年、2001年和2011年在FOCS會議上發(fā)表過的論文。
本次共有7篇論文獲得該獎項，其中1991年3篇，2001年3篇，2011年1篇。
最后，附上論文鏈接們~
最佳論文鏈接：
https://eccc.weizmann.ac.il/report/2021/081/
最佳學生論文鏈接：
https://arxiv.org/abs/2106.02026
參考鏈接：
https://focs2021.cs.colorado.edu/
— 完 —
- 蘋果芯片主管也要跑路！庫克被曝出現(xiàn)健康問題2025-12-07
- 世界模型和具身大腦最新突破：90%生成數(shù)據(jù)，VLA性能暴漲300%｜開源2025-12-02
- 谷歌新架構(gòu)突破Transformer超長上下文瓶頸！Hinton靈魂拷問：后悔Open嗎？2025-12-05
- 90后華人副教授突破30年數(shù)學猜想！結(jié)論與生成式AI直接相關(guān)2025-11-26
