顶会最佳论文覆灭科学家们30多年期待：复杂度远超预期

AIGC动态欢迎阅读

原标题：顶会最佳论文覆灭科学家们30多年期待：复杂度远超预期

关键字：算法,度量,消耗,空间,路径

文章来源：量子位

内容字数：5953字

内容摘要：克雷西 发自 凹非寺量子位 | 公众号 QbitAI三十多年来，在线算法一直被科学家寄予厚望，但一篇论文的诞生让它走下了神坛。它的目标，简单来说就是在没有完整数据的情况下，通过有限的信息提前找到最佳策略。在我们的生活中，例如股票市场的即时交易分析，还有导航路径的实时规划，都有在线算法的身影。不过没有完整数据，就意味着性能将受到限制；因此科学家们一直期待它能突破数据的桎梏，达到更高的效率。然而就在最近，来自微软研究院、牛津大学等机构的研究人员在进行了一场实验之后发现，这种算法的复杂度远远超过了人们的期待。他们也凭借着这篇论文，在今年的计算理论顶会STOC上获得了最佳论文奖。那么，他们获奖的这项研究，具体说了些什么呢？科学家们的“30年期待”这里我们需要先来了解一些背景知识。和在线算法相对的，还有离线算法，它在开始处理之前需要先接收到所有的输入数据。由于预先掌握了完整数据，在同等的数据规模下离…

原文链接：点此阅读原文：顶会最佳论文覆灭科学家们30多年期待：复杂度远超预期

联系作者

文章来源：量子位

作者微信：QbitAI

作者简介：追踪人工智能新趋势，关注科技行业新突破