转自：量子位
计算机理论顶会FOCS 各项论文奖项已公布。
最佳学生论文奖被MIT华人学霸毛啸收入囊中。
而姚期智院士和达摩院量子实验室负责人施尧耘则凭借2001年发表的论文《Informationl Complexity and the Direct Sum Problem for Simultaneous Message Complexity》，获得时间检验奖。
另外，最佳论文奖由来自印度理工学院、丹麦奥胡斯大学等多家研究机构的国际团队获得。
作为中国计算机学会（CCF）推荐的计算机科学理论方向A类会议，FOCS这样的顶会被公认为是计算机科学领域难度最大、含金量最高的会议。
FOCS 将于2月7日-10日在美国科罗拉多州丹佛市举办。
论文详情，我们具体来看。
最佳学生论文奖：打破未加权树编辑距离问题三次障碍
n节点树的（非加权）树编辑距离问题要求计算两个带节点标签的有根树之间的相似度。
目前的最佳算法时间复杂度为O（n3）。同一篇论文还表明，O（n3）是任何使用了所谓分解策略的算法的最佳运行时间。
根据APSP猜想，该问题无法在亚立方时间内解决。
但本文作者用一种时间复杂度为O（n2.9546）的算法解决了未加权的树编辑距离问题，打破了三次障碍。
作者考虑了一个等价的最大化问题，并使用了一种设计具有许多特殊属性的矩阵的动态编程方案。通过使用分解方案以及一些组合技术，将树编辑距离减少到有界差分矩阵的最大加乘积，真正在亚立方时间内解决问题。
论文作者毛啸曾就读于长沙雅礼中学，是国际奥林匹克信息学竞赛（IOI）银牌得主。
他高中毕业时，在MIT全奖和清华保送之间，选择了到MIT攻读计算机科学和数学相关专业。
今年，他刚刚本科毕业，现为MIT工程学硕士。
此前，他的MIT校友、姚班毕业生陈立杰也曾获FOCS 最佳学生论文奖。
姚期智、施尧耘2001年论文获时间检验奖
姚期智院士此番凭借他和Amit Chakrabarti、施尧耘、Anthony Wirth合著的《Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity》获颁FOCS 时间检验奖。
这篇论文探讨的是同步消息复杂度的直和问题，并引入了新的信息复杂度概念。
给定同一个问题的m个副本，是否需要m倍的资源才能解决这m个问题？这就是直和问题。这篇论文在姚期智提出的同步消息（SM）传播模型中研究了这个问题。
这是FOCS第三次颁出时间检验奖。颁奖对象是1991年、2001年和在FOCS会议上发表过的论文。
本次共有7篇论文获得该奖项，其中1991年3篇，2001年3篇，1篇。
最后，附上论文链接们~
最佳论文链接：
https://eccc.weizmann.ac.il/report//081/
最佳学生论文链接：
/abs/2106.02026
参考链接：
https://focs.cs.colorado.edu/
推荐阅读
【重磅】斯坦福李飞飞《注意力与Transformer》总结，84页ppt开放下载！
仅需12层网络，在ImageNet上准确率达到80.7%！普林斯顿大学最新提出ParNet！
MobileViT: 一种更小，更快，高精度的轻量级Transformer端侧网络架构（附代码实现）
【移动端最强架构】LCNet吊打现有主流轻量型网络（附代码实现）
基于Attention机制的轻量级网络架构以及代码实现
深度学习中的轻量级网络架构总结与代码实现
一文详解Inception家族的前世今生（从InceptionV1-V4、Xception）附全部代码实现
华为实验室诺亚方舟实验室招聘视觉感知算法实习生
欢迎大家加入DLer-计算机视觉&Transformer群！
大家好，这是计算机视觉&Transformer论文分享群里，群里会第一时间发布最新的Transformer前沿论文解读及交流分享会，主要设计方向有：图像分类、Transformer、目标检测、目标跟踪、点云与语义分割、GAN、超分辨率、视频超分、人脸检测与识别、动作行为与时空运动、模型压缩和量化剪枝、迁移学习、人体姿态估计等内容。
进群请备注：研究方向+学校/公司+昵称（如Transformer+上交+小明）
👆长按识别，邀请您进群！
