An official website of the United States government
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
Concise tensors of minimal border rank
We determine defining equations for the set of concise tensors of minimal border rank in Cm⊗Cm⊗Cm when m = 5 and the set of concise minimal border rank 1∗-generic tensors when m = 5, 6. We solve the classical problem in algebraic complexity theory of classifying minimal border rank tensors in the special case m = 5. Our proofs utilize two recent developments: the 111-equations defined by Buczy´nska–Buczy´nski and results of Jelisiejew–Šivic on the variety of commuting matrices. We introduce a new algebraic invariant of a concise tensor, its 111-algebra, and exploit it to give a strengthening of Friedland’s normal form for 1-degenerate tensors satisfying Strassen’s equations. We use the 111-algebra to characterize wild minimal border rank tensors and classify them in C5⊗C5⊗C5.
more »
« less
- Award ID(s):
- 2203618
- PAR ID:
- 10399504
- Date Published:
- Journal Name:
- Mathematische Annalen
- ISSN:
- 0025-5831
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)We make a first geometric study of three varieties inCm⊗Cm⊗Cm (for eachm), including the Zariski closure of the set of tight tensors, the tensors with continuous regular symmetry. Our motivation is to develop a geometric framework for Strassen’s asymptotic rank conjecture that the asymptotic rank of any tight tensor is minimal. In particular, we determine the dimension of the set of tight tensors. We prove that this dimension equals the dimension of the set of oblique tensors, a less restrictive class introduced by Strassen.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
-
This is a survey primarily about determining the border rank of tensors, especially those relevant for the study of the complexity of matrix multiplication. This is a subject that on the one hand is of great significance in theoretical computer science, and on the other hand touches on many beautiful topics in algebraic geometry such as classical and recent results on equations for secant varieties (e.g., via vector bundle and representation-theoretic methods) and the geometry and deformation theory of zero dimensional schemes.more » « less
-
Ta-Shma, Amnon (Ed.)The Tensor Isomorphism problem (TI) has recently emerged as having connections to multiple areas of research within complexity and beyond, but the current best upper bound is essentially the brute force algorithm. Being an algebraic problem, TI (or rather, proving that two tensors are non-isomorphic) lends itself very naturally to algebraic and semi-algebraic proof systems, such as the Polynomial Calculus (PC) and Sum of Squares (SoS). For its combinatorial cousin Graph Isomorphism, essentially optimal lower bounds are known for approaches based on PC and SoS (Berkholz & Grohe, SODA '17). Our main results are an Ω(n) lower bound on PC degree or SoS degree for Tensor Isomorphism, and a nontrivial upper bound for testing isomorphism of tensors of bounded rank. We also show that PC cannot perform basic linear algebra in sub-linear degree, such as comparing the rank of two matrices (which is essentially the same as 2-TI), or deriving BA=I from AB=I. As linear algebra is a key tool for understanding tensors, we introduce a strictly stronger proof system, PC-Inv, which allows as derivation rules all substitution instances of the implication AB=I → BA=I. We conjecture that even PC-Inv cannot solve TI in polynomial time either, but leave open getting lower bounds on PC-Inv for any system of equations, let alone those for TI. We also highlight many other open questions about proof complexity approaches to TI.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/s00208-023-02569-y
