Tensors and symmetry at the heart of computational complexity theory

Abstract: Tensors are a 3D (and higher) analogue of matrices: whereas matrices capture pairwise interactions, tensors can capture k-way interactions for any k. In this talk I weave a tale connecting much of my work over the past several years, in which tensors and symmetry will be seen to arise over and over again in central problems in computational complexity theory. In particular, I will discuss how they arise in three central problems:

1) algorithms for multiplying matrices
2) complexity lower bounds such as the geometric complexity theory program towards P versus NP, and
3) algorithms for testing isomorphism of groups (a special case of the graph isomorphism problem).

In all three of these problems, it turns out that symmetry and symmetry-breaking of the underlying tensors plays an important role, which has led to many of my most significant results.

Bio: Joshua A. Grochow is an Assistant Professor in the Departments of Computer Science and (by courtesy) Mathematics at the University of Colorado Boulder, where he is a member of the CS Theory Group and the Complex Systems Group. He was previously an Omidyar Fellow at the interdisciplinary Santa Fe Institute for complex systems. Prior to SFI, he did a postdoc in the University of Toronto CS Theory Group, and got his Ph.D. at the University of Chicago.

https://cuboulder.zoom.us/j/190280621