Subquadratic 3SUM and Subcubic APSP
8 hours ago
- 该论文首次提出了对3SUM和全对最短路径（APSP）的教科书算法的多项式改进，分别在O(n^1.9992)和O(n^2.9995)时间内求解。
- 它反驳了几个假设，包括3SUM、APSP、精确三角形、零权重k-团和矩形在线矩阵向量猜想。
- 这些结果源于一种新的薄矩阵乘积算法，该算法在O(N^2/D^0.063)时间内计算选定的条目，比完整计算快多项式级。
- 该算法使用Schönhage的十乘法恒等式修改了Coppersmith的矩形矩阵乘法，仅处理所需的操作。
- 它在稀疏的不平衡三部图上以真正的次二次时间解决了全边稀疏三角形问题，该问题可归约为精确三角形、3SUM和APSP。
- 一种数据结构版本支持对未知的矩阵乘积的单个条目进行查询。