Η κατάρριψη των κλασικών υποθέσεων
Για δεκαετίες, τα προβλήματα 3SUM και All-Pairs Shortest Paths (APSP) θεωρούνταν θεμελιώδη σημεία αναφοράς στην υπολογιστική πολυπλοκότητα, με τα «εγχειριδιακά» όρια να θεωρούνται σχεδόν αδιαπέραστα. Η πρόσφατη εργασία των ερευνητών εισάγει μια ριζική αλλαγή, επιτυγχάνοντας πολυωνυμικές βελτιώσεις που καταρρίπτουν τις υποθέσεις (hypotheses) που βασίζονταν στη δυσκολία αυτών των προβλημάτων.
Αρχιτεκτονική του νέου αλγορίθμου
Ο πυρήνας της ανακάλυψης έγκειται σε έναν νέο αλγόριθμο για τον πολλαπλασιασμό πινάκων με συγκεκριμένες ιδιότητες (thin matrix products). Βασιζόμενοι σε μια παραλλαγή του αλγορίθμου του Coppersmith για ορθογώνιους πίνακες, οι ερευνητές χρησιμοποίησαν την ταυτότητα δέκα πολλαπλασιασμών του Schönhage. Η καινοτομία έγκειται στον περιορισμό των πράξεων μόνο στα απαραίτητα στοιχεία (entries) του πίνακα, επιτυγχάνοντας υπολογιστικό κόστος σημαντικά χαμηλότερο από τον πλήρη πολλαπλασιασμό.
Επιπτώσεις στη θεωρητική πληροφορική
Η δυνατότητα επίλυσης του προβλήματος All-Edges Sparse Triangle σε χρόνο subquadratic ανοίγει νέους δρόμους για μια πληθώρα άλλων προβλημάτων που ανάγονται (reduce) σε αυτό. Η εργασία δεν περιορίζεται μόνο σε θεωρητικό επίπεδο, καθώς προτείνει και μια δομή δεδομένων ικανή να απαντά σε ερωτήματα για μεμονωμένα στοιχεία του γινομένου πινάκων, προσφέροντας πρακτική αξία πέρα από την ασυμπτωτική βελτίωση.