魚羊 發自 凹非寺

量子位 報道 | 公眾號 QbitAI

計算機理論頂會FOCS 2021各項論文獎項已公佈。

最佳學生論文獎被MIT華人學霸毛嘯收入囊中。

而姚期智院士和達摩院量子實驗室負責人施堯耘則憑藉2001年發表的論文《Informationl Complexity and the Direct Sum Problem for Simultaneous Message Complexity》，獲得時間檢驗獎。

另外，最佳論文獎由來自印度理工學院、丹麥奧胡斯大學等多家研究機構的國際團隊獲得。

作為中國計算機學會（CCF）推薦的計算機科學理論方向A類會議，FOCS這樣的頂會被公認為是計算機科學領域難度最大、含金量最高的會議。

FOCS 2021將於2022年2月7日-10日在美國科羅拉多州丹佛市舉辦。

論文詳情，我們具體來看。

最佳學生論文獎：打破未加權樹編輯距離問題三次障礙

n節點樹的（非加權）樹編輯距離問題要求計算兩個帶節點標籤的有根樹之間的相似度。

目前的最佳演算法時間複雜度為O（n3）。同一篇論文還表明，O（n3）是任何使用了所謂分解策略的演算法的最佳執行時間。

根據APSP猜想，該問題無法在亞立方時間內解決。

但本文作者用一種時間複雜度為O（n2.9546）的演算法解決了未加權的樹編輯距離問題，打破了三次障礙。

作者考慮了一個等價的最大化問題，並使用了一種設計具有許多特殊屬性的矩陣的動態程式設計方案。透過使用分解方案以及一些組合技術，將樹編輯距離減少到有界差分矩陣的最大加乘積，真正在亞立方時間內解決問題。

論文作者毛嘯曾就讀於長沙雅禮中學，是2017年國際奧林匹克資訊學競賽（IOI）銀牌得主。

他高中畢業時，在MIT全獎和清華保送之間，選擇了到MIT攻讀計算機科學和數學相關專業。

今年，他剛剛本科畢業，現為MIT工程學碩士。

此前，他的MIT校友、姚班畢業生陳立傑也曾獲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會議上發表過的論文。

本次共有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/

— 完 —

量子位 QbitAI · 頭條號簽約

關注我們，第一時間獲知前沿科技動態