3SUMとAPSPの仮説を初めて反証、教科書的アルゴリズムを多項式的に改善

Subquadratic 3SUM and Subcubic APSP

3SUMをO(n^1.9992)、APSPをO(n^2.9995)で決定論的に解く初のアルゴリズムを提示し、長年信じられてきた3SUM仮説とAPSP仮説を反証する。鍵となるのは疎な歪んだ三部分グラフ上の三角形問題を真に準二次時間で解く、thin matrix productの新アルゴリズムだ。Exact Triangle仮説やZero-Weight k-Clique仮説、van den Brand、Nanongkai、Saranurakによる3つの矩形ヒンティングOnline Matrix-Vector予想も同時に否定される。