Irreversibility of structure tensors of modules

• Wojtala, Maciej ^[1]
  1. [1] University of Warsaw

     University of Warsaw

     Warszawa, Polonia

     
• Localización: Collectanea mathematica, ISSN 0010-0757, Vol. 74, Fasc. 2, 2023, págs. 487-499
• Idioma: inglés
• DOI: 10.1007/s13348-022-00361-w
• Texto completo no disponible (Saber más ...)
• Resumen

  • Determining the matrix multiplication exponent \omega is one of the greatest open problems in theoretical computer science. We show that it is impossible to prove \omega = 2 by starting with structure tensors of modules of fixed degree and using arbitrary restrictions. It implies that the same is impossible by starting with 1_A-generic non-diagonal tensors of fixed size with minimal border rank. This generalizes the work of Bläser and Lysikov (Slice rank of block tensors and irreversibility of structure tensors of algebras 170, 2020). Our methods come from both commutative algebra and complexity theory.

• Referencias bibliográficas
  • Alman, J., Williams; Virginia V.: Further Limitations of the Known Approaches for Matrix Multiplication In: 9th Innovations in theoretical...
  • Alman, J., Williams; Virginia V.: Limits on all known (and some unknown) approaches to matrix multiplication In: 59th Annual IEEE symposium...
  • Blaser, M.; Lysikov, V.: Slice rank of block tensors and irreversibility of structure tensors of algebras In: 45th International symposium...
  • Blasiak, J., et al.: On cap sets and the group-theoretic approach to matrix multiplication In: Discrete analysis . issn: 2397-3129.(Jan. 2017)...
  • Blasiak, J., et al.: Which groups are amenable to proving exponent two for matrix multiplication? (2017) arXiv: 1712.02302 [math.GR]
  • Brion, M.: Sur l’image de l’application moment In: Séminaire d’Algèbre Paul Dubreil et Marie-Paule Malliavin: Proceedings, Paris 1986, volume...
  • Burgisser, P.; Clausen, M.; Shokrollahi, M.A.: Algebraic complexity theory. Vol. 315. Springer Science & Business Media, (2013)
  • Christandl, M.; Vrana, P.; Zuiddam, J.: Barriers for fast matrix multiplication from irreversibility . In: 34th Computational complexity conference....
  • Coppersmith, D.; Winograd, S.: Matrix multiplication via arithmetic progressions. In: J. Symbolic Comput. 9.3 , pp. 2510-280. issn: 0747-7171....
  • Davie, A. M., Stothers, A. J.: Improved bound for complexity of matrix multiplication. In: Proceedings of the royal society of edinburgh:...
  • Jelisiejew, J.; Šivic, K.: Components and singularities of Quot schemes and varieties of commuting matrices. arXiv: 2106.13137 [math.AG] (2021)
  • Landsberg, J.M.; Michałek, M.: Abelian tensors. In: Journal de Mathématiques Pures et Appliquées 108.3 , pp. 333–371 (2017)
  • Gall, F.L.: Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th international symposium on symbolic and algebraic...
  • Zuiddam, J.; Christandl, M.; Vrana, P.: Universal points in the asymptotic spectrum of tensors. In: arXiv: 1709.07851 (2017)
  • Strassen, V.: Gaussian elimination is not optimal. In: Numerische mathematik 13.4, pp. 354–356(1969)
  • Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. In: STOC 12.(2012)