姚期智施尧耘获FOCS 2021时间检验奖,MIT华人学霸毛啸摘最佳学生论文奖

2021 年 12 月 25 日 量子位
鱼羊 发自 凹非寺
量子位 报道 | 公众号 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/

本文系网易新闻•网易号特色内容激励计划签约账号【量子位】原创内容,未经账号授权,禁止随意转载。

「智能汽车」交流群招募中!

欢迎关注智能汽车、自动驾驶的小伙伴们加入社群,与行业大咖交流、切磋,不错过智能汽车行业发展&技术进展。

ps.加好友请务必备注您的姓名-公司-职位哦~


点这里👇关注我,记得标星哦~

一键三连「分享」、「点赞」和「在看」

科技前沿进展日日相见~


登录查看更多
0

相关内容

IEEE计算机科学基础研讨会(FOCS)是由IEEE计算机学会计算数学基础技术委员会(TCMF)主办的旗舰会议,涵盖了广泛的理论计算机科学。它每年秋季举行,并与每年春季举行的由ACM SIGACT赞助的姊妹会议——计算理论年度研讨会(STOC)配对。官网链接:http://ieee-focs.org/
CVPR 2020 最佳论文与最佳学生论文!
专知会员服务
35+阅读 · 2020年6月17日
【课程】概率图模型,卡内基梅隆大学邢波
专知会员服务
69+阅读 · 2019年11月4日
AAAI 2019最佳论文公布,CMU、斯坦福、MIT上榜
新智元
12+阅读 · 2019年1月28日
国家自然科学基金
1+阅读 · 2016年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
11+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年4月30日
国家自然科学基金
3+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2022年4月20日
Arxiv
0+阅读 · 2022年4月19日
Arxiv
0+阅读 · 2022年4月19日
VIP会员
相关基金
国家自然科学基金
1+阅读 · 2016年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
11+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年4月30日
国家自然科学基金
3+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员