QLunch: Harold Nieuwboer

Speaker: Harold Nieuwboer

Title: Asymptotic tensor rank is characterized by polynomials

Abstract: Asymptotic tensor rank is notoriously difficult to determine. Indeed, determining its value for the 2×2 matrix multiplication tensor would determine the matrix multiplication exponent, a long-standing open problem. On the other hand, Strassen's asymptotic rank conjecture makes the bold claim that asymptotic tensor rank equals the largest dimension of the tensor and is thus as easy to compute as matrix rank. Despite tremendous interest, much is still unknown about the structural and computational properties of asymptotic rank.

We prove that the sublevel sets of asymptotic tensor rank are Zariski-closed (just like for matrix rank). While we do not exhibit the defining polynomials explicitly, their mere existence has strong implications on the structure of asymptotic rank. As one such implication, we find that the values that asymptotic tensor rank takes, on all tensors, is a well-ordered set. Previously such discreteness results were only known for finite fields or for other tensor parameters (e.g., asymptotic slice rank). We obtain them for infinite fields like the complex numbers. Another implication is that for every upper bound r, there exists a polynomial-time algorithm that determines whether a tensor's asymptotic rank is at most r.

Based on joint work with Matthias Christandl, Koen Hoeberechts, Péter Vrana and Jeroen Zuiddam, https://arxiv.org/abs/2411.15789.

Zoom link to the QLunch talk: 

https://ucph-ku.zoom.us/j/65819801238?pwd=yjil7pb0GaUstIaabcLiO1JsBbdpPx.1