Nous donnons les premières améliorations polynomiales par rapport aux algorithmes classiques pour 3SUM et les plus courts chemins entre toutes paires (APSP) : nous montrons comment résoudre de manière déterministe 3SUM sur n entiers de taille polynomiale en temps O(n^{1.9992}) et APSP sur des graphes orientés à n sommets avec des poids entiers polynomialement bornés en temps O(n^{2.9995}). Cela réfute les hypothèses 3SUM et APSP. En utilisant des réductions connues, nous réfutons également les versions à valeurs réelles des hypothèses 3SUM et APSP, l'hypothèse du triangle exact, les hypothèses de k-clique de poids nul, et les trois conjectures rectangulaires de matrice-vecteur en ligne de van den Brand, Nanongkai et Saranurak, et nous donnons des accélérations polynomiales pour une variété d'autres problèmes.
Tous ces résultats découlent d'un seul nouvel algorithme pour les produits de matrices minces. Soit X une matrice entière N×D et Y une matrice entière D×N avec D ≤ N^{1/18}, et soit W tout ensemble d'au plus N^2/√D positions. Nous calculons les entrées (XY)[I, J], (I, J)∈W, en O(N^2/D^{0.063}) opérations, ce qui est polynomialement moins que le temps nécessaire pour écrire XY ou pour calculer N^2/√D produits scalaires un par un.
Nous concevons cet algorithme en modifiant une variante de l'algorithme de multiplication de matrices rectangulaires de Coppersmith, construit à partir d'une identité de dix multiplications de Schönhage, pour effectuer uniquement les opérations nécessaires pour les entrées dans W, et montrons que peu d'opérations sont nécessaires. Interprété comme un algorithme de graphe, cela résout le problème du triangle creux de toutes les arêtes en temps vraiment sous-quadratique sur des graphes tripartites creux déséquilibrés où deux parties ont n sommets mais une partie a n^{ε} sommets pour ε<0.12. Par des réductions connues, le triangle exact, et donc 3SUM et APSP, se réduisent à ce problème.
Nous donnons également une version de structure de données qui répond aux requêtes pour des entrées individuelles de XY, non connues à l'avance. Historique de soumission : De Josh Alman [voir l'e-mail] [v1]Lun, 5 oct. 2026 17:44:29 UTC (93 Ko).
Source: Hacker News · Résumé par HeadlinesBriefing