姚期智施堯耘獲FOCS 2021時(shí)間檢驗(yàn)獎(jiǎng)，MIT華人學(xué)霸毛嘯摘最佳學(xué)生論文獎(jiǎng)

魚羊 2021-12-25 14:31:05 來(lái)源：量子位

計(jì)算機(jī)理論頂會(huì)FOCS論文獎(jiǎng)項(xiàng)頒出

魚羊發(fā)自凹非寺

量子位報(bào)道 | 公眾號(hào) QbitAI

計(jì)算機(jī)理論頂會(huì)FOCS 2021各項(xiàng)論文獎(jiǎng)項(xiàng)已公布。

最佳學(xué)生論文獎(jiǎng)被MIT華人學(xué)霸毛嘯收入囊中。

姚期智施堯耘獲FOCS 2021時(shí)間檢驗(yàn)獎(jiǎng)，MIT毛嘯摘最佳學(xué)生論文獎(jiǎng)

而姚期智院士和達(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)由來(lái)自印度理工學(xué)院、丹麥奧胡斯大學(xué)等多家研究機(jī)構(gòu)的國(guó)際團(tuán)隊(duì)獲得。

作為中國(guó)計(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日在美國(guó)科羅拉多州丹佛市舉辦。

論文詳情，我們具體來(lái)看。

最佳學(xué)生論文獎(jiǎng)：打破未加權(quán)樹編輯距離問(wèn)題三次障礙

n節(jié)點(diǎn)樹的（非加權(quán)）樹編輯距離問(wèn)題要求計(jì)算兩個(gè)帶節(jié)點(diǎn)標(biāo)簽的有根樹之間的相似度。

目前的最佳算法時(shí)間復(fù)雜度為O（n3）。同一篇論文還表明，O（n3）是任何使用了所謂分解策略的算法的最佳運(yùn)行時(shí)間。

根據(jù)APSP猜想，該問(wèn)題無(wú)法在亞立方時(shí)間內(nèi)解決。

但本文作者用一種時(shí)間復(fù)雜度為O（n2.9546）的算法解決了未加權(quán)的樹編輯距離問(wèn)題，打破了三次障礙。

作者考慮了一個(gè)等價(jià)的最大化問(wèn)題，并使用了一種設(shè)計(jì)具有許多特殊屬性的矩陣的動(dòng)態(tài)編程方案。通過(guò)使用分解方案以及一些組合技術(shù)，將樹編輯距離減少到有界差分矩陣的最大加乘積，真正在亞立方時(shí)間內(nèi)解決問(wèn)題。

論文作者毛嘯曾就讀于長(zhǎng)沙雅禮中學(xué)，是2017年國(guó)際奧林匹克信息學(xué)競(jìng)賽（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ù)雜度的直和問(wèn)題，并引入了新的信息復(fù)雜度概念。

給定同一個(gè)問(wèn)題的m個(gè)副本，是否需要m倍的資源才能解決這m個(gè)問(wèn)題？這就是直和問(wèn)題。這篇論文在姚期智提出的同步消息（SM）傳播模型中研究了這個(gè)問(wèn)題。