On the Complexity of Isomorphism Problems for Tensors, Groups, Polynomials, and Algebras

This lecture from the Computer Science/Discrete Mathematics Seminar II explores the complexity of isomorphism problems across various algebraic structures. Delve into how 3-tensor isomorphism (defined as transformations via multiplication with three invertible matrices) captures the complexity of testing isomorphism for polynomials, certain group families, and associative or Lie algebras. Learn about the newly introduced "Tensor Isomorphism" complexity class and its connections to cryptography, quantum information, number theory, and geometry. Discover recent algorithmic breakthroughs for tensor isomorphism over finite fields that surpass the decades-old n^log(n) barrier for class-2 p-group isomorphism. The talk presents collaborative research with Joshua Grochow, Gábor Ivanyos, Xiaorui Sun, Katherine Stange, Yinan Li, Markus Bläser, Antoine Joux, and Chuanqi Zhang.