Powers of Tensors and Fast Matrix Multiplication
Not on the map. Why?
Abstract (arXiv)
This paper presents a method to analyze the powers of a given trilinear form (a special kind of algebraic constructions also called a tensor) and obtain upper bounds on the asymptotic complexity of matrix multiplication. Compared with existing approaches, this method is based on convex optimization, and thus has polynomial-time complexity. As an application, we use this method to study powers of the construction given by Coppersmith and Winograd [Journal of Symbolic Computation, 1990] and obtain the upper bound ω<2.3728639 on the exponent of square matrix multiplication, which slightly improves the best known upper bound.
Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). First posted on arXiv 30 Jan 2014.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 6; 2022: 2; 2023: 3.
11 papers.
- 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
- 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
- 2021DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Searchcited by 8
- 2023Convergence of Two-Layer Regression with Nonlinear Unitscited by 6
- 2021Fast Graph Neural Tangent Kernel via Kronecker Sketchingcited by 2
- 2023Regret-Optimal Federated Transfer Learning for Kernel Regression with Applications in American Option Pricingcited by 2
- 2021Deep-Learning Based Linear Precoding for MIMO Channels with Finite-Alphabet Signalingcited by 1
- 2022Matrix Multiplication: Verifying Strong Uniquely Solvable Puzzlescited by 1
- 2021Fine-Grained Complexity and Algorithms for the Schulze Voting Methodcited by 0
- 2021Gradient-based Data Subversion Attack Against Binary Classifierscited by 0
- 2022A Structured Sparse Neural Network and Its Matrix Calculations Algorithmcited by 0
- 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time14 Sep 2023
- 2023Regret-Optimal Federated Transfer Learning for Kernel Regression with Applications in American Option Pricing8 Sep 2023
- 2023Convergence of Two-Layer Regression with Nonlinear Units16 Aug 2023
- 2022Matrix Multiplication: Verifying Strong Uniquely Solvable Puzzles30 Dec 2022
- 2022A Structured Sparse Neural Network and Its Matrix Calculations Algorithm2 Jul 2022
- 2021Fast Graph Neural Tangent Kernel via Kronecker Sketching4 Dec 2021
- 2021Deep-Learning Based Linear Precoding for MIMO Channels with Finite-Alphabet Signaling5 Nov 2021
- 2021DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search6 Jul 2021
- 2021Gradient-based Data Subversion Attack Against Binary Classifiers31 May 2021
- 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing18 May 2021
- 2021Fine-Grained Complexity and Algorithms for the Schulze Voting Method5 Mar 2021