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 withinvertible 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 threeinvertible matrices along the three directions. In this talk we explore tensor isomorphism through the lenses of complexity, algorithms, andcryptography. 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 somerecent advances. These support the use of tensor isomorphism in cryptography, such as the securitybasis 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 fromTsinghua University in 2012, supervised by Andrew Yao and László Babai. Youming is interested incomputational complexity and algebraic computation. Some specific problems he has worked oninclude polynomial identity testing and isomorphism problems of algebraic structures.