Vi presenterar en ny kombinatorial algoritm för triangelfynd och boolesk matris multiplikation som körs i O(n 3 / log 4 n) tid, där notation undertrycker poly(logg) faktorer. Detta förbättrar den tidigare bästa kombinatoriska algoritmen av Chan [4] som körs i 3 / log 3 n) tid. Vår algoritm generaliserar split-and-conquer-strategin för Chans algoritm. Dessutom föreslår vi en allmän ram för att upptäcka trianglar i grafer och beräkna Boolesk matrismultiplikation. Ungefär, om vi kan hitta de "lätta delarna" av en given instans effektivt, kan vi lösa hela problemet snabbare än n 3.
För närvarande, den snabbaste sådan algoritm körs asymptotiskt i Timê O(n 3 /log 4 n) REF.
An Improved Combinatorial Algorithm for Boolean Matrix Multiplication
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}