theoretical-cs

一篇 Reddit 讨论帖，聚焦 **Scott Aaronson** 关于「数学末日（Mathocalypse）」的文章——一位理论计算机科学家坦率地谈了谈 AI 有可能让人类在数学和理论计算机科学领域的工作变得过时这件事。

本文改进了随机适当在线学习的最优期望错误界，表明其为 O(L(H) log T)，这在通用常数范围内对于最坏情况类别是最优的。

一则传闻称 P = NP，据称存在一种能在 O(n^{极大数}) 时间内解决 3-SAT 的方法，这显得不太可信或带有幽默色彩。

Scott Aaronson 报道称，有传言说人工智能公司，可能是 OpenAI，在解决理论计算机科学中长期存在的开放问题上取得了重大进展，但由于最近的争议，正在推迟宣布。

这篇论文通过证明工作函数算法在每个度量空间上达到竞争比为 k，从而证明了 k-server 猜想。

本文讨论了如果P vs NP问题得到构造性解决的潜在短期和长期影响，据报道像OpenAI和Anthropic这样的组织正在研究此问题，并邀请数学和理论计算机科学领域的专家分享见解。

本文探讨了关于计算机科学是否本质上与计算机相关的辩论，引用历史观点和个人反思来质疑该领域的本质。

本文介绍了 sync heap，一种新颖的数据结构，它将删除操作与揭示被删除元素解耦，使得在有限检查下插入和删除操作具有常数摊销时间复杂度，并将一个教科书中的调度问题从 O(n log n) 改进到 O(n)。

来自清华、斯坦福和马克斯·普朗克的五位研究人员开发了一种新的最短路径算法，在稀疏有向图中超越了迪杰斯特拉算法，实现了O(m log^(2/3) n)的时间复杂度，这是自1987年以来的首次改进。