3SUM и APSP впервые решены быстрее классических алгоритмов
Subquadratic 3SUM and Subcubic APSP
Новая работа опровергает гипотезы 3SUM и APSP: предложены детерминированные алгоритмы со временем O(n^1.9992) для 3SUM и O(n^2.9995) для APSP. В основе — алгоритм для произведения тонких матриц, который решает задачу All-Edges Sparse Triangle на разреженных асимметричных графах. Это также опровергает гипотезы Exact Triangle, Zero-Weight k-Clique и три гипотезы Online Matrix-Vector, давая полиномиальные ускорения для многих задач.
Мы даём первые полиномиальные улучшения над классическими алгоритмами для 3SUM и All-Pairs Shortest Paths (APSP): мы показываем, как детерминированно решить 3SUM на n целых числах полиномиального размера за время O(n^1.9992) и APSP на ориентированных графах с n вершинами с полиномиально ограниченными целочисленными весами за время O(n^2.9995).