Seminar: Tensor Isomorphism: complexity, algorithms, and cryptography
10 Jul 2025
02.00 PM - 03.00 PM
ABN Conference Room 1-1
Current Students, Industry/Academic Partners
Abstract
Two matrices are called equivalent if one can be transformed into the other by multiplying with invertible matrices on the left and right. Extending this idea to 3-tensors, it is natural to define two 3-tensors as isomorphic if they can be transformed into one another by multiplication with three invertible matrices along the three directions. In this talk we explore tensor isomorphism through the lenses of complexity, algorithms, and cryptography. Starting from complexity, we will examine how tensor isomorphism relates to well-known problems such as graph isomorphism, code equivalence, and group isomorphism. Compared to graph isomorphism, tensor isomorphism seems a much harder algorithmic problem, despite some recent advances. These support the use of tensor isomorphism in cryptography, such as the security basis of some digital signature schemes.
Biography
Youming Qiao is an associate professor at University of Technology Sydney. In the first half of 2025, he is also a member at the Institute for Advanced Study, Princeton. Youming obtained his PhD from Tsinghua University in 2012, supervised by Andrew Yao and László Babai. Youming is interested in computational complexity and algebraic computation. Some specific problems he has worked on include polynomial identity testing and isomorphism problems of algebraic structures.