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

Preprint · Eli Shamir

- Archive id: arxiv:1806.08974
- Published: 2018-06-23
- arXiv: https://arxiv.org/abs/1806.08974
- Source URL: https://arxiv.org/abs/1806.08974
- PDF: https://arxiv.org/pdf/1806.08974
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.