计算机理论顶会 FOCS 2021 奖项揭示
发布时间：2021-12-26 14:25:34 所属栏目：动态 来源：互联网
导读：计算机理论顶会 FOCS 2021 各项论文奖项已公布，最佳学生论文奖被 MIT 华人学霸毛啸收入囊中。 而姚期智院士和达摩院量子实验室负责人施尧耘则凭借 2001 年发表的论文《Informationl Complexity and the Direct Sum Problem for Simultaneous Message Complex
|
计算机理论顶会 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）的算法解决了未加权的树编辑距离问题，打破了三次障碍。 作者考虑了一个等价的最大化问题，并使用了一种设计具有许多特殊属性的矩阵的动态编程方案。通过使用分解方案以及一些组合技术，将树编辑距离减少到有界差分矩阵的最大加乘积，真正在亚立方时间内解决问题。 （编辑：东莞站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐