PapersMulti-sourceSelected

Rectangular matrix multiplication bound improved via shared-leg entropy

Rectangular matrix multiplication from shared-leg entropy

Why we picked it

Rectangular matrix multiplication exponents govern the cost of graph and dynamic-programming algorithms, so a proven bound of ω(1,1/2,1)=2 turns into concrete runtime drops, including the O(n^2.4999) shortest-path result. Theoretical computer scientists and algorithm engineers tracking how OpenAI's entropy-based technique spreads through complexity theory will want the proof details. The arXiv note is open access, so the full constructions can be checked directly.

A new arXiv note (2610.10494v1) extends OpenAI's recent matrix-multiplication analysis to rectangular products.

Body

It proves ω(1,k,1) ≤ 2 for 0 ≤ k ≤ 1/2 and ω(1,k,1) ≤ 1+k+1/(4k) for k ≥ 1/2, giving ω(1,1/2,1)=2 and dual exponent α ≥ 1/2.

The proof uses the shared-leg entropy inequality and polynomial-multiplication degenerations, with a spectral constraint b ≤ 4a(1-a) from bounding intercepts.

As applications, Zwick's all-pairs shortest paths algorithm runs in O(n^2.5), and combining with the (min,+)-product result of Alman and Vassilevska Williams yields O(n^2.

4999).

Original · arXiv: OpenAI

Rectangular matrix multiplication from shared-leg entropy

In this note, we extend the analysis underlying a recent matrix-multiplication result by OpenAI to rectangular products and prove that $ω(1,k,1)\le 2$ for $0\le k\le \frac{1}{2}$ and $ω(1,k,1)\le 1+k+\frac{1}{4k}$ for $k\ge \frac{1}{2}$. In particular, $ω(1,\frac{1}{2},1)=2$ and the dual exponent satisfies $α\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.

Industry Coordinates & Source Verification

This report is categorized under AITOP's "Papers" desk, focusing on US frontier AI labs and Silicon Valley technology leaders. Key entities and technical topics under continuous tracking include matrix multiplication, arXiv, OpenAI.

Primary source verification: published directly by arXiv: OpenAI with first-party authority. Cross-source corroboration: 11 independent sources have covered this development (including rohanpaul_ai, kimmonismus, 宝玉), confirming industry-wide signal strength.