[Theory] UC Theory Seminar

[Alexander Razborov via Theory]

Youming Qiao
University of Technology, Sydney
 
 
  
Tuesday, May 13, 2025, at 3:30pm
Location: Kent 102
 
 
 
Title: Tensor Isomorphism: complexity, algorithms, and cryptography

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. 

Finally, we shall indicate how Tensor Isomorphism over Z naturally leads to connections with Calabi--Yau threefolds and Bhargava's approach to Gauss composition laws.

Based on joint work with many collaborators, including Josh Grochow, Gábor Ivanyos, Xiaorui Sun, Kate Stange, and more. 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250507/b2cfd828/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 197811 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250507/b2cfd828/attachment-0001.jpg>