Interactions between invariant theory and complexity theory

Speaker: 

Visu Markam

Affiliation: 

Institute for Advanced Study and University of Melbourne

Date: 

Thu, 25/02/2021 - 12:00pm

Venue: 

Zoom link: https://unsw.zoom.us/j/89348779322

Abstract: 

The study of symmetries in the setting of group actions via "invariant" polynomials is called invariant theory. Computation has played a key role in the evolution of invariant theory from its very beginnings with "masters of computation" such as Gordan, Sylvester, Cayley, etc in the mid 19th century. Over the last two decades, new directions in invariant theory have emerged from connections to computational complexity, the subject dedicated to understanding rigorously the notion of computational efficiency. In this talk, I will discuss how fundamental problems in complexity such as graph isomorphism, identity testing and even the celebrated P vs NP problem arise in the context of invariant theory. I will explain how developments in invariant theory can inform and make progress in complexity theory and in particular illustrate this in the case of identity testing. Towards the end, I will try to give a glimpse of the various directions in which this rapidly expanding field is headed. Based on joint works with Harm Derksen, Ankit Garg, Christian Ikenmeyer, Rafael Oliveira, Michael Walter, and Avi Wigderson.

School Seminar Series: