Contexte et hypothèses

Depuis plusieurs décennies, les algorithmes de référence pour le problème 3SUM et le problème All-Pairs Shortest Paths (APSP) atteignent respectivement les complexités O(n^2) et O(n^3). Ces performances sont à la base des 3SUM hypothesis et APSP hypothesis, qui postulent l’impossibilité de les améliorer de façon polynomialement significative. L’article d’Alman et Vassilevska Williams propose le premier dépassement polynomial de ces limites, en présentant des algorithmes déterministes dont les temps d’exécution sont O(n^{1.9992}) pour 3SUM et O(n^{2.9995}) pour APSP sur des graphes dirigés à poids entiers polynomialement bornés.

Algorithme de produit matriciel mince

Le cœur de la contribution repose sur un nouveau procédé de multiplication de matrices « minces ». Soient X une matrice N×D et Y une matrice D×N, avec la contrainte D ≤ N^{1/18}. L’algorithme ne calcule que les N^2/√D entrées spécifiées par un ensemble W (|W| ≤ N^2/√D) et le fait en O(N^2/D^{0.063}) opérations. Cette amélioration provient d’une adaptation de l’algorithme de multiplication rectangulaire de Coppersmith, lui-même basé sur une identité à dix multiplications de Schönhage. En ne réalisant que les opérations nécessaires aux positions de W, le nombre total d’opérations devient strictement inférieur au coût d’écriture complet de XY ou à la réalisation naïve de N^2/√D produits scalaires.

Applications aux problèmes 3SUM et APSP

Interprété comme un problème de graphe, le produit matriciel mince résout le All-Edges Sparse Triangle sur des graphes tripartites lopsided où deux parties contiennent n sommets et la troisième n^{ε} sommets, avec ε < 0.12. Les réductions classiques montrent que Exact Triangle se ramène à ce problème, et que Exact Triangle à son tour implique 3SUM et APSP. Ainsi, le temps sous‑quadratique obtenu pour le problème de triangles entraîne directement les temps O(n^{1.9992}) pour 3SUM et O(n^{2.9995}) pour APSP. En outre, les auteurs démontrent que ces améliorations invalident également les versions réelles des hypothèses 3SUM et APSP, la Exact Triangle hypothesis, les hypothèses Zero‑Weight k‑Clique, ainsi que les trois conjectures rectangulaires d’Online Matrix‑Vector proposées par van den Brand, Nanongkai et Saranurak.

Limites et perspectives

Le gain polynomial dépend de deux paramètres stricts : la largeur D doit rester inférieure à N^{1/18} et le facteur d’asymétrie ε doit être inférieur à 0.12. Ces conditions limitent l’applicabilité directe aux graphes denses ou aux matrices où D est proportionnel à N. De plus, le modèle suppose des poids entiers de taille polynomialement bornée, excluant les poids réels ou exponentiellement grands. Malgré ces restrictions, la méthode introduit un paradigme nouveau : exploiter des identités algébriques avancées pour ne calculer que les entrées réellement requises, ouvrant la voie à d’autres problèmes où la sortie est « sparse ». Une version data‑structure du procédé, capable de répondre à des requêtes ponctuelles sur XY sans connaître W à l’avance, est également présentée, suggérant des applications potentielles en bases de données et en calcul distribué.