RANK AND BORDER RANK OF KRONECKER POWERS OF TENSORS AND STRASSEN'S LASER METHOD Academic Article uri icon

abstract

  • AbstractWe prove that the border rank of the Kronecker square of the little CoppersmithWinograd tensor $$T_{cw,q}$$ T c w , q is the square of its border rank for $$q > 2$$ q > 2 and that the border rank of its Kronecker cube is the cube of its border rank for $$q > 4$$ q > 4 . This answers questions raised implicitly by Coppersmith & Winograd (1990, 11) and explicitly by Blser (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 CoppersmithWinograd 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 CoppersmithWinograd tensor, $$T_{skewcw,q}$$ T s k e w c w , q . For $$q = 2$$ q = 2 , the Kronecker square of this tensor coincides with the $$3 imes 3$$ 3 3 determinant polynomial, $$det_{3} in mathbb{C}^{9} otimes mathbb{C}^{9} otimes mathbb{C}^{9}$$ det 3 C 9 C 9 C 9 , 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 $$det_3$$ det 3 , exhibiting a strict submultiplicative behaviour for $$T_{skewcw,2}$$ T s k e w c w

published proceedings

  • COMPUTATIONAL COMPLEXITY

altmetric score

  • 1

author list (cited authors)

  • Conner, A., Gesmundo, F., Landsberg, J. M., & Ventura, E.

citation count

  • 4

complete list of authors

  • Conner, Austin||Gesmundo, Fulvio||Landsberg, Joseph M||Ventura, Emanuele

publication date

  • June 2022