Pith. sign in

REVIEW 1 cited by

Faster Matrix Multiplication via Asymmetric Hashing

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 2210.10173 v5 pith:JOFI4O7H submitted 2022-10-18 cs.DS

Ran Duan , Hongxun Wu , Renfei Zhou This is my paper · ORCID
classification cs.DS
keywords matrixmultiplicationboundmethodomegaanalyzingasymmetricfast
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

Fast matrix multiplication is one of the most fundamental problems in algorithm research. The exponent of the optimal time complexity of matrix multiplication is usually denoted by $\omega$. This paper discusses new ideas for improving the laser method for fast matrix multiplication. We observe that the analysis of higher powers of the Coppersmith-Winograd tensor [Coppersmith & Winograd 1990] incurs a "combination loss", and we partially compensate for it using an asymmetric version of CW's hashing method. By analyzing the eighth power of the CW tensor, we give a new bound of $\omega<2.371866$, which improves the previous best bound of $\omega<2.372860$ [Alman & Vassilevska Williams 2020]. Our result breaks the lower bound of $2.3725$ in [Ambainis, Filmus & Le Gall 2015] because of the new method for analyzing component (constituent) tensors.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. OpenAlex reports about 9 citations worldwide. Full citation record

  1. Asymptotic tensor rank is characterized by polynomials

    cs.CC 2024-11 conditional novelty 8.0 of 10

    Sublevel sets of asymptotic tensor rank are Zariski-closed, making the parameter well-ordered in value, complete over the complex numbers, and computable from above.

Pith tools