More Like this

1. Constructing Spanning Sets of Affine Algebraic Curvature Tensors

   Kelly, Stephen (May 2023, Rose Hulman Undergraduate Mathematics Journal)

   In this paper, we construct two spanning sets for the affine algebraic curvature tensors. We then prove that every 2-dimensional affine algebraic curvature tensor can be represented by a single element from either of the two spanning sets. This paper provides a means to study affine algebraic curvature tensors in a geometric and algebraic manner similar to previous studies of canonical algebraic curvature tensors. 

   more » « less
2. Concise tensors of minimal border rank

   https://doi.org/10.1007/s00208-023-02569-y  

   Jelisiejew, Joachim; Landsberg, J. M.; Pal, Arpan (April 2023, Mathematische Annalen)

   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
3. Geometric rank of tensors and subrank of matrix multiplication

   Kopparty, S; Moshkovitz, G; Zuiddam, J. (March 2020, Electronic colloquium on computational complexity)

   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
4. Leibniz International Proceedings in Informatics (LIPIcs):38th Computational Complexity Conference (CCC 2023)

   https://doi.org/10.4230/LIPIcs.CCC.2023.4  

   Galesi, Nicola; Grochow, Joshua A.; Pitassi, Toniann; She, Adrian (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   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
5. Curvature operators and rational cobordism

   https://doi.org/10.1016/j.aim.2024.109995  

   Bettiol, Renato G; Goodman, McFeely Jackson (December 2024, Advances in Mathematics)

   We determine linear inequalities on the eigenvalues of curvature operators that imply vanishing of the twisted A-hat genus on a closed Riemannian spin manifold, where the twisting bundle is any prescribed parallel bundle of tensors. These inequalities yield surgery-stable curvature conditions tailored to annihilate further rational cobordism invariants, such as the Witten genus, elliptic genus, signature, and even the rational cobordism class itself. 

   more » « less