One of the main open problems in theoretical computer science is bounding the exponent of matrix multiplication. To produce a bound on the exponent, one picks a tensor of minimal border rank. The space of such tensors is an algebraic variety akin to moduli spaces such as the Hilbert scheme of points. It can be effectively investigated using algebraic methods, but there has been little work in this direction yet. In the talk I will review the complexity background and explain what is known about this space. I will also mention related open questions which are of algebraic and arithmetic flavor. No prior knowledge of tensors, complexity etc. is expected or indeed necessary.
Deformation theory of tensors and matrix multiplication
28.03.2023 13:15 - 14:45
Organiser:
H. Grobner, A. Mellit
Location: