Istnieją dowody, że mnożenie macierzy jest w

Powszechnie uważa się, że dla wszystkich $\epsilon > 0$ możliwe jest pomnożenie dwóch macierzy $n \times n$ w czasie $O(n^{2 + \epsilon})$ . Trochę dyskusji jest tutaj .

Zapytałem niektórych ludzi, którzy są bardziej zaznajomieni z badaniami, czy myślą, że istnieje $k>0$ niezależne od $n$ tak że istnieje algorytm $O(n^2 \log^k n)$ do mnożenia macierzy i wydaje się, że w przeważającej części mają intuicję, że odpowiedź brzmi „nie”, ale nie mogła wyjaśnić, dlaczego. Oznacza to, że wierzą, że możemy to zrobić w czasie $O(n^{2.001})$ , ale nie w czasie $O(n^2 \log^{100} n)$ .

Jakie są powody, by sądzić, że nie ma algorytmu $O(n^2 \log^k n)$ przy stałym $k>0$ ?

Istnieje algorytm mnożenia macierzy $N \times N^{0.172}$ macierz $N^{0.172} \times N$ w operacjach arytmetycznych $N^2 \operatorname{polylog}\left(N\right)$ . Główna tożsamość zastosowana w tym dokumencie pochodzi z pracy Coppersmitha „Szybkie mnożenie prostokątnych macierzy”, ale wyjaśnienie, dlaczego prowadzi do polilogu $N^2 \operatorname{polylog}\left(N\right)$ zamiast $N^{2 + \epsilon}$ znajduje się w dodatku do artykułu Williamsa , „Nowe algorytmy oraz dolne granice dla obwodów z liniowymi bramkami progowymi ".

Działa to tylko dlatego, że tożsamość Coppersmith ma dodatkową strukturę, z której można skorzystać, a nowsze algorytmy MM nie wydają się mieć takiej struktury. To powiedziawszy, nie jestem pewien, dlaczego nie można spodziewać się rozszerzenia tego podejścia na mnożenie macierzy $N \times N \times N$

$A_\epsilon$$O(n^{2+\epsilon})$$O(n^2 poly(\log n))$

$O(n^2 poly(\log n))$

Josh Alman pokazał kilka fajnych wyników MM w dolnej granicy, które zdobyły nagrodę CCC 2019 dla najlepszego papieru studenckiego! http://drops.dagstuhl.de/opus/volltexte/2019/10834/pdf/LIPIcs-CCC-2019-12.pdf