计算机理论顶会 FOCS 2021 奖项揭晓:MIT 华人学霸毛啸获得最佳学生论文奖
消息来源:baojiabao.com 作者: 发布时间:2024-05-15
计算机理论顶会 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 篇。
最后,附上论文链接~
最佳论文链接:点此直达
最佳学生论文链接:点此直达
2022-05-08 05:51:53相关文章
- 美国法院裁定阿里须为Squishmallows玩具侵权案答辩
2023-12-28 19:59:34
- 小米汽车传员工3700人 雷军称小米汽车不可能卖9万9
2023-12-28 19:41:57
- 国家新闻出版署:认真研究《网络游戏管理办法(草桉徵求意见稿)》关切 实行前进一步完善
2023-12-28 19:14:56
- 天猫新规可以无条件申请“仅退款”了?淘宝天猫又离狗多多零元购近了一步
2023-12-28 18:57:55
- 印度以打击金融犯罪为由逮捕了两名 vivo 高管
2023-12-26 16:49:01
- 在国外微信收不到国内信息?微信和WeChat将被拆分
2023-12-15 10:40:15
- 苹果iPhone15 系列手机发布最新消息 预计上市发布时间9月
2023-08-06 23:21:02
- 华为将发布鸿蒙HarmonyOS4操作系统 功能五大升级支持设备清单
2023-08-06 23:17:37
- 整治自媒体网红账号 400万粉丝网红发布擦边视频被无限期封禁
2023-07-12 09:56:09
- 网传微信文件传输助手是真人是真的吗?微信官方回应
2023-06-27 15:53:32
- 电信移动送手机成了“信用购”?你上了运营商的贷款套路了吗?
2023-06-12 17:18:55
- 中国电信广东地区崩了无信号 客服回应已在核实处理
2023-06-08 15:39:04
- 消息称小米新能源汽车价格表正讨论定价区间:双版本不同配置,高配或超 35 万元
2023-03-06 12:56:03
- 华为因制裁被传或分拆剥离手机业务? 内部人士回应:可能性不大.
2023-03-05 23:26:41
- OPPO正式发布安第斯智能云,让终端更智能
2023-02-24 16:02:27
- 华为与OPPO签订全球专利交叉许可协议 包括5G蜂窝通信专利
2023-02-24 16:02:26
- 老蛙将推MINI镜头新品:目前未知具体规格 官宣将于12月20日发布
2023-02-24 16:02:26
- 首发全新35mm定制光学系统 努比亚Z50性能同样强悍
2023-02-24 16:02:25
- Redmi K60屏幕细节曝光:全系标配2K护眼柔性直屏+5000mAh大容量电池
2023-02-24 16:02:25
- OPPO Find N2今天发 合金金属折叠屏更轻了
2023-02-24 16:02:24