Metraipolis › archive › dc_438e88e2d756

Rectangular matrix multiplication from shared-leg entropy — arXiv:2610.10494

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.10494
License (as archived)
CC0-1.0
Archived
2026-10-08T12:49:49.308Z
SHA-256 of the archived text
200c8e97ed2d14a3a34b191ee1bd66bb10ada6dfdcbe24ff2cc8d2a0757c2501
Stable URL of this page
https://metraipolis.com/documento/dc_438e88e2d756

How to cite

Rectangular matrix multiplication from shared-leg entropy — arXiv:2610.10494 — arXiv (en), https://arxiv.org/abs/2610.10494 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_438e88e2d756 (Metraipolis archive dc_438e88e2d756, sha256 200c8e97ed2d14a3a34b191ee1bd66bb10ada6dfdcbe24ff2cc8d2a0757c2501)
BibTeX
@misc{dc438e88e2d756,
  title = {Rectangular matrix multiplication from shared-leg entropy — arXiv:2610.10494},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.10494},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_438e88e2d756; sha256 200c8e97ed2d14a3a34b191ee1bd66bb10ada6dfdcbe24ff2cc8d2a0757c2501},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.10494. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In this note, we extend the analysis underlying a recent matrix-multiplication result by OpenAI to rectangular products and prove that $\omega(1,k,1)\le 2$ for $0\le k\le \frac{1}{2}$ and $\omega(1,k,1)\le 1+k+\frac{1}{4k}$ for $k\ge \frac{1}{2}$. In particular, $\omega(1,\frac{1}{2},1)=2$ and the dual exponent satisfies $\alpha\ge \frac{1}{2}$. We use the shared-leg entropy inequality and polynomial-multiplication degenerations from that work, retaining two-leg symmetry and the orientation of each sector. Logarithmic averaging produces homogeneous auxiliary profiles. Their powered versions have a common asymptotic slope, and bounding their intercepts gives the spectral constraint $b\le 4a(1-a)$. This yields the rectangular curve by tensor-spectrum duality. As an application, Zwick's algorithm for all-pairs shortest paths in directed unweighted graphs runs in $O(n^{2.5})$ time. Combining the rectangular bound with the $(\min,+)$-product improvement of Alman and Vassilevska Williams further gives $O(n^{2.4999})$ running time.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.10494 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:19:30.212Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).