計(jì)算機(jī)理論頂會(huì) FOCS 2021 各項(xiàng)論文獎(jiǎng)項(xiàng)已公布，最佳學(xué)生論文獎(jiǎng)被 MIT 華人學(xué)霸毛嘯收入囊中。
而姚期智院士和達(dá)摩院量子實(shí)驗(yàn)室負(fù)責(zé)人施堯耘則憑借 2001 年發(fā)表的論文《Informationl Complexity and the Direct Sum Problem for Simultaneous Message Complexity》，獲得時(shí)間檢驗(yàn)獎(jiǎng)。
另外，最佳論文獎(jiǎng)由來自印度理工學(xué)院、丹麥奧胡斯大學(xué)等多家研究機(jī)構(gòu)的國際團(tuán)隊(duì)獲得。
作為中國計(jì)算機(jī)學(xué)會(huì)（CCF）推薦的計(jì)算機(jī)科學(xué)理論方向 A 類會(huì)議，F(xiàn)OCS 這樣的頂會(huì)被公認(rèn)為是計(jì)算機(jī)科學(xué)領(lǐng)域難度最大、含金量最高的會(huì)議。
FOCS 2021 將于 2022 年 2 月 7 日-10 日在美國科羅拉多州丹佛市舉辦。
論文詳情，我們具體來看。
最佳學(xué)生論文獎(jiǎng)：打破未加權(quán)樹編輯距離問題三次障礙
n 節(jié)點(diǎn)樹的（非加權(quán)）樹編輯距離問題要求計(jì)算兩個(gè)帶節(jié)點(diǎn)標(biāo)簽的有根樹之間的相似度。
目前的最佳算法時(shí)間復(fù)雜度為 O（n3）。同一篇論文還表明，O（n3）是任何使用了所謂分解策略的算法的最佳運(yùn)行時(shí)間。
根據(jù) APSP 猜想，該問題無法在亞立方時(shí)間內(nèi)解決。
但本文作者用一種時(shí)間復(fù)雜度為 O（n2.9546）的算法解決了未加權(quán)的樹編輯距離問題，打破了三次障礙。
作者考慮了一個(gè)等價(jià)的最大化問題，并使用了一種設(shè)計(jì)具有許多特殊屬性的矩陣的動(dòng)態(tài)編程方案。通過使用分解方案以及一些組合技術(shù)，將樹編輯距離減少到有界差分矩陣的最大加乘積，真正在亞立方時(shí)間內(nèi)解決問題。
論文作者毛嘯曾就讀于長沙雅禮中學(xué)，是 2017 年國際奧林匹克信息學(xué)競賽（IOI）銀牌得主。
他高中畢業(yè)時(shí)，在 MIT 全獎(jiǎng)和清華保送之間，選擇了到 MIT 攻讀計(jì)算機(jī)科學(xué)和數(shù)學(xué)相關(guān)專業(yè)。
今年，他剛剛本科畢業(yè)，現(xiàn)為 MIT 工程學(xué)碩士。
此前，他的 MIT 校友、姚班畢業(yè)生陳立杰也曾獲 FOCS 2019 最佳學(xué)生論文獎(jiǎng)。
姚期智、施堯耘 2001 年論文獲時(shí)間檢驗(yàn)獎(jiǎng)
姚期智院士此番憑借他和 Amit Chakrabarti、施堯耘、Anthony Wirth 合著的《Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity》獲頒 FOCS 2021 時(shí)間檢驗(yàn)獎(jiǎng)。
這篇論文探討的是同步消息復(fù)雜度的直和問題，并引入了新的信息復(fù)雜度概念。
給定同一個(gè)問題的 m 個(gè)副本，是否需要 m 倍的資源才能解決這 m 個(gè)問題？這就是直和問題。這篇論文在姚期智提出的同步消息（SM）傳播模型中研究了這個(gè)問題。
這是 FOCS 第三次頒出時(shí)間檢驗(yàn)獎(jiǎng)。頒獎(jiǎng)對象是 1991 年、2001 年和 2011 年在 FOCS 會(huì)議上發(fā)表過的論文。
本次共有 7 篇論文獲得該獎(jiǎng)項(xiàng)，其中 1991 年 3 篇，2001 年 3 篇，2011 年 1 篇。
最后，附上論文鏈接~
最佳論文鏈接：點(diǎn)此直達(dá)
最佳學(xué)生論文鏈接：點(diǎn)此直達(dá)
廣告聲明：文內(nèi)含有的對外跳轉(zhuǎn)鏈接（包括不限于超鏈接、二維碼、口令等形式），用于傳遞更多信息，節(jié)省甄選時(shí)間，結(jié)果僅供參考，IT之家所有文章均包含本聲明。