Pith. sign in

REVIEW 3 cited by

More Asymmetry Yields Faster Matrix Multiplication

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2404.16349 v2 pith:UEKH7SJ3 submitted 2024-04-25 cs.DS cs.CC

Josh Alman , Ran Duan , Virginia Vassilevska Williams , Yinzhan Xu , Zixuan Xu , Renfei Zhou This is my paper · ORCID
classification cs.DScs.CC
keywords matrixmethodmultiplicationasymmetryboundimprovementomegayields
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

We present a new improvement on the laser method for designing fast matrix multiplication algorithms. The new method further develops the recent advances by [Duan, Wu, Zhou FOCS 2023] and [Vassilevska Williams, Xu, Xu, Zhou SODA 2024]. Surprisingly the new improvement is achieved by incorporating more asymmetry in the analysis, circumventing a fundamental tool of prior work that requires two of the three dimensions to be treated identically. The method yields a new bound on the square matrix multiplication exponent $$\omega<2.371339,$$ improved from the previous bound of $\omega<2.371552$. We also improve the bounds of the exponents for multiplying rectangular matrices of various shapes.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. All-Pairs Shortest Paths with Few Weights per Node

    cs.DS 2025-06 conditional novelty 8.0 of 10

    Node-Weighted APSP is solvable in Õ(n^{2.686}) time (n^{2.5} if omega=2), and APSP with at most n^{3-omega-delta} distinct weights per node is solvable in subcubic time.

  2. Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities

    quant-ph 2025-07 conditional novelty 6.0 of 10

    Quantum algorithms for bandits with knapsacks achieve improved regret and time complexity by replacing classical sampling with quantum Monte Carlo and approximate quantum LP solving.

  3. Flip Graphs for Polynomial Multiplication

    cs.SC 2025-02 conditional novelty 6.0 of 10

    Over large fields, flip graphs connect the naive polynomial multiplication algorithm to an optimal Toom-Cook algorithm in a cubic number of flips and reductions.

Pith tools