姚期智施堯耘獲FOCS 2021時(shí)間檢驗(yàn)獎(jiǎng)，MIT華人學(xué)霸毛嘯摘最佳學(xué)生論文獎(jiǎng)
計(jì)算機(jī)理論頂會(huì)FOCS論文獎(jiǎng)項(xiàng)頒出
魚(yú)羊 發(fā)自 凹非寺
量子位 報(bào)道 | 公眾號(hào) QbitAI
計(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)由來(lái)自印度理工學(xué)院、丹麥奧胡斯大學(xué)等多家研究機(jī)構(gòu)的國(guó)際團(tuán)隊(duì)獲得。
作為中國(guó)計(jì)算機(jī)學(xué)會(huì)（CCF）推薦的計(jì)算機(jī)科學(xué)理論方向A類(lèi)會(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)樹(shù)編輯距離問(wèn)題三次障礙
n節(jié)點(diǎn)樹(shù)的（非加權(quán)）樹(shù)編輯距離問(wèn)題要求計(jì)算兩個(gè)帶節(jié)點(diǎn)標(biāo)簽的有根樹(shù)之間的相似度。
目前的最佳算法時(shí)間復(fù)雜度為O（n3）。同一篇論文還表明，O（n3）是任何使用了所謂分解策略的算法的最佳運(yùn)行時(shí)間。
根據(jù)APSP猜想，該問(wèn)題無(wú)法在亞立方時(shí)間內(nèi)解決。
但本文作者用一種時(shí)間復(fù)雜度為O（n2.9546）的算法解決了未加權(quán)的樹(shù)編輯距離問(wèn)題，打破了三次障礙。
作者考慮了一個(gè)等價(jià)的最大化問(wèn)題，并使用了一種設(shè)計(jì)具有許多特殊屬性的矩陣的動(dòng)態(tài)編程方案。通過(guò)使用分解方案以及一些組合技術(shù)，將樹(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)專(zhuā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)題。
這是FOCS第三次頒出時(shí)間檢驗(yàn)獎(jiǎng)。頒獎(jiǎng)對(duì)象是1991年、2001年和2011年在FOCS會(huì)議上發(fā)表過(guò)的論文。
本次共有7篇論文獲得該獎(jiǎng)項(xiàng)，其中1991年3篇，2001年3篇，2011年1篇。
最后，附上論文鏈接們~
最佳論文鏈接：
https://eccc.weizmann.ac.il/report/2021/081/
最佳學(xué)生論文鏈接：
https://arxiv.org/abs/2106.02026
參考鏈接：
https://focs2021.cs.colorado.edu/
— 完 —
- 標(biāo)準(zhǔn)化3D生成質(zhì)量榜單來(lái)了！首創(chuàng)層次化評(píng)價(jià)體系，告別“誰(shuí)的demo更吸睛”主觀評(píng)估2025-08-16
- 阿里閃電入局Agent Infra！智能體新基建亮相WAIC，“超級(jí)大腦”開(kāi)箱即用2025-07-31
- 世紀(jì)華通謝斐：在“三大平衡”中領(lǐng)跑，實(shí)現(xiàn)游戲行業(yè)更高質(zhì)量的發(fā)展2025-08-01
- 1.5B參數(shù)撬動(dòng)“吉卜力級(jí)”全能體驗(yàn)，國(guó)產(chǎn)開(kāi)源之光多模態(tài)統(tǒng)一模型，來(lái)了2025-07-30
相關(guān)閱讀
他99年出生，本科身份摘FOCS 2021最佳學(xué)生論文獎(jiǎng)，曾4刷NOI金牌
高中畢業(yè)于長(zhǎng)沙雅禮中學(xué)
姚期智領(lǐng)銜提出大模型「思維」框架！邏輯推理正確率達(dá)98%，思考方式更像人類(lèi)了
超越思維鏈、思維樹(shù)
