# Faster Matrix Multiplication via Asymmetric Hashing

Preprint · Ran Duan, Hongxun Wu, Renfei Zhou

- Archive id: arxiv:2210.10173
- Published: 2022-10-18
- arXiv: https://arxiv.org/abs/2210.10173
- Source URL: https://arxiv.org/abs/2210.10173
- PDF: https://arxiv.org/pdf/2210.10173
- Provenance: arxiv

## 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 $ω$. 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 $ω\<2.371866$, which improves the previous best bound of $ω\<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.

_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.