An official website of the United States government
Determining the asymptotic algebraic complexity of matrix multiplication, succinctly represented by the matrix multiplication exponent omega, is a central problem in algebraic complexity theory. The best upper bounds on omega, leading to the state-of-the-art omega <= 2.37.., have been obtained via the laser method of Strassen and its generalization by Coppersmith and Winograd. Recent barrier results show limitations for these and related approaches to improve the upper bound on omega. We introduce a new and more general barrier, providing stronger limitations than in previous work. Concretely, we introduce the notion of "irreversibility" of a tensor and we prove (in some precise sense) that any approach that uses an irreversible tensor in an intermediate step (e.g., as a starting tensor in the laser method) cannot give omega = 2. In quantitative terms, we prove that the best upper bound achievable is lower bounded by two times the irreversibility of the intermediate tensor. The quantum functionals and Strassen support functionals give (so far, the best) lower bounds on irreversibility. We provide lower bounds on the irreversibility of key intermediate tensors, including the small and big Coppersmith - Winograd tensors, that improve limitations shown in previous work. Finally, we discuss barriers on the group-theoretic approach in terms of "monomial" irreversibility.
more »
« less
Geometric rank of tensors and subrank of matrix multiplication
Motivated by problems in algebraic complexity theory (e.g., matrix multiplication) and extremal combinatorics (e.g., the cap set problem and the sunflower problem), we introduce the geometric rank as a new tool in the study of tensors and hypergraphs. We prove that the geometric rank is an upper bound on the subrank of tensors and the independence number of hypergraphs. We prove that the geometric rank is smaller than the slice rank of Tao, and relate geometric rank to the analytic rank of Gowers and Wolf in an asymptotic fashion. As a first application, we use geometric rank to prove a tight upper bound on the (border) subrank of the matrix multiplication tensors, matching Strassen's well-known lower bound from 1987.
more »
« less
- PAR ID:
- 10169288
- Date Published:
- Journal Name:
- Electronic colloquium on computational complexity
- Volume:
- 27
- Issue:
- 29
- ISSN:
- 1433-8092
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We prove that the border rank of the Kronecker square of the little Coppersmith–Winograd tensor Tcw,q is the square of its border rank for q > 2 and that the border rank of its Kronecker cube is the cube of its border rank for q > 4. This answers questions raised implicitly by Coppersmith & Winograd (1990, §11) and explicitly by Bl¨aser (2013, Problem 9.8) and rules out the possibility of proving new upper bounds on the exponent of matrix multiplication using the square or cube of a little Coppersmith–Winograd tensor in this range. In the positive direction, we enlarge the list of explicit tensors potentially useful for Strassen’s laser method, introducing a skew-symmetric version of the Coppersmith– Winograd tensor, Tskewcw,q. For q = 2, the Kronecker square of this tensor coincides with the 3 × 3 determinant polynomial, det3 ∈ C9 ⊗ C9 ⊗ C9, regarded as a tensor. We show that this tensor could potentially be used to show that the exponent of matrix multiplication is two. We determine new upper bounds for the (Waring) rank and the (Waring) border rank of det3, exhibiting a strict submultiplicative behaviour for Tskewcw,2 which is promising for the laser method. We establish general results regarding border ranks of Kronecker powers of tensors, and make a detailed study of Kronecker squares of tensors in C3 ⊗ C3 ⊗ C3.more » « less
-
We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give optimal algorithms. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously known barriers, both in the numerical sense, as well as in its generality. We prove our result using the asymptotic spectrum of tensors. More precisely, we crucially make use of two families of real tensor parameters with special algebraic properties: the quantum functionals and the support functionals. In particular, we prove that any lower bound on the dual exponent of matrix multiplication α via the big Coppersmith–Winograd tensors cannot exceed 0.625.more » « less
-
We answer a question, posed implicitly in [P. Bürgisser et al., 1997] and explicitly in [M. Bläser, 2013], showing the border rank of the Kronecker square of the little Coppersmith-Winograd tensor is the square of the border rank of the tensor for all q>2, a negative result for complexity theory. We further show that when q>4, the analogous result holds for the Kronecker cube. In the positive direction, we enlarge the list of explicit tensors potentially useful for the laser method. We observe that a well-known tensor, the 3 × 3 determinant polynomial regarded as a tensor, det_3 ∈ C^9 ⊗ C^9 ⊗ C^9, could potentially be used in the laser method to prove the exponent of matrix multiplication is two. Because of this, we prove new upper bounds on its Waring rank and rank (both 18), border rank and Waring border rank (both 17), which, in addition to being promising for the laser method, are of interest in their own right. We discuss "skew" cousins of the little Coppersmith-Winograd tensor and indicate why they may be useful for the laser method. We establish general results regarding border ranks of Kronecker powers of tensors, and make a detailed study of Kronecker squares of tensors in C^3 ⊗ C^3 ⊗ C^3.more » « less
-
In the light bulb problem, one is given uniformly random vectors x1,…,xn,y1,…,yn∈{−1,1}d. They are all chosen independently except a planted pair (xi∗,yj∗) is chosen with correlation ρ>0. The goal is to find the planted pair. This problem was introduced over 30 years ago by L.~Valiant, and is known to have many applications in data analysis, statistics, and learning theory. The naive algorithm runs in Ω(n2) time, and algorithms based on Locality-Sensitive Hashing approach quadratic time as ρ→0. In 2012, G.~Valiant gave a breakthrough algorithm using fast matrix multiplication that runs in time O(n(5−ω)/(4−ω))0 is. This was subsequently refined by Karppa, Kaski, and Kohonen in 2016 to O(n2ω/3)0. We also introduce a new tensor T2112, which has the same size of 2×2 matrix multiplication tensor, but runs faster than the Strassen's algorithm for light bulb problem.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
