2022/10/18 by Ran Duan, Hongxun Wu, Duan, Ran +3 · 9 citations
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.2210.10173
openalex publication_date 2022/10/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.