Almost optimal Boolean matrix multiplication [BMM]-by multi-encoding of rows and columns

Abstract

The Boolean product $R = P \cdot Q$ of two $\{ 0, 1\} \; m \times m \; $ matrices is $$R(j,k) = 1 \; \mathrm{\ IF\ for\ some\ } \; t \; \,P(j, t) = Q(t, k) = 1\; \; \mathrm{ELSE\ } \, R(j, k) = 0. $$ The near-optimal design reduces the complexity of computing $R$ from the standard $m^3$ to $O(m^{(2+e)})$, for arbitrary small $e > 0$, by a practical algorithm. This renders reduced complexity to several graph-property tests: Finding triangles and higher-size cliques; finding all-pairs shortest paths, and more. Also, parsing a string $w$ by a context-free grammar is reduced to near quadratic in $w$-size. The design uses several distinct 2-digit encodings: $j$ by $(j_1, j_2), \; k \, $ by $\, (k_1, k_2)$. Each one gives rise to bunches of short digraphs from sources $j$'s to sinks $k$'s via switching nodes, and walks between them. The combined information, using the Chinese remainder theorem, leads to the correct values of $R(j, k)$.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.