Audio is streamed directly from the publisher (dts-api.xiaoyuzhoufm.com) as published in their RSS feed. Play Podcasts does not host this file. Rights-holders can request removal through the copyright & takedown page.
Show Notes
Seventy3：借助NotebookLM的能力进行论文解读，专注人工智能、大模型、机器人算法、crypto方向，让大家跟着AI一起进步。
今天的主题是：
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Summary
我们提出了一种确定性算法，在**比较–加法模型（comparison-addition model）下，用于求解带有实数非负边权的有向图单源最短路径（SSSP）**问题，其时间复杂度为O(mlog2/3n)。
这是首个在稀疏图上打破 Dijkstra 算法 O(m+nlogn) 时间复杂度界限的结果，表明 Dijkstra 算法并非 SSSP 问题的最优算法。
原文链接：https://arxiv.org/abs/2504.17033