我々は、3SUMと全点対最短経路（APSP）の教科書アルゴリズムに対する最初の多項式的改善を与える：多項式サイズのn個の整数上の3SUMを決定的にO(n^{1.9992})時間で解き、多項式有界整数重みを持つ有向n頂点グラフ上のAPSPをO(n^{2.9995})時間で解く方法を示す。これは3SUMとAPSPの仮説を反駁する。既知の還元を用いて、3SUMとAPSPの仮説の実数値版、正確な三角形仮説、ゼロ重みk-クリーク仮説、およびvan den Brand、Nanongkai、Saranurakの3つの長方形ヒント付きオンラインマトリックス・ベクトル予想も反駁し、さまざまな他の問題に対する多項式的高速化を与える。これらの結果はすべて、薄い行列積のための単一の新しいアルゴリズムに由来する。XをN×D整数行列、YをD×N整数行列（D ≤ N^{1/18}）とし、Wを最大N^2/√D個の位置の任意の集合とする。我々はエントリ(XY)[I, J]、(I, J)∈WをO(N^2/D^{0.063})演算で計算する。これはXYを書き出すか、N^2/√D個の内積を1つずつ計算するのに必要な時間よりも多項式的に少ない。このアルゴリズムは、Coppersmithの長方形行列乗算アルゴリズムの変種を修正して設計され、Schönhageの10乗算恒等式に基づき、W内のエントリに必要な演算のみを実行し、必要な演算が少ないことを示す。グラフアルゴリズムとして解釈すると、これはスパースな非対称三部グラフ上の全辺スパース三角形問題を真の準二次時間で解く。ここで、2つの部分はn頂点を持つが、1つの部分はε<0.12に対してn^{ε}頂点を持つ。既知の還元により、正確な三角形、したがって3SUMとAPSPはこの問題に帰着する。また、事前に知られていないXYの単一エントリのクエリに答えるデータ構造バージョンも提供する。提出履歴：Josh Almanから[メールを表示][v1]2026年10月5日月曜日17:44:29 UTC（93 KB）
出典: Hacker News · 要約：HeadlinesBriefing