Abstract
Many computational problems are invariant under certain input symmetries. For some this is apparent, and for others less so. The main point of this lecture is that using these symmetries can be essential both for obtaining better algorithms for these problems, as well and proving hardness results for them. Furthermore, understanding these symmetries reveal connections between disparate problems from many different disciplines.
This talk will introduce these connections of symmetries to algorithms and complexity through a series of examples. It will also give a short introduction to Invariant Theory, which studies group actions, their orbits and invariants, and provide the tools which underlie most recent progress in this direction. The lecture following this one will continue and describe a comprehensive algorithmic theory for a large class of problems possessing such symmetries.
This talk requires no special background. It is based on many joint works in the past 5 years, with Zeyuan Allen-Zhu, Peter Burgisser, Cole Franks, Ankit Garg, Leonid Gurvits, Pavel Hrubes, Yuanzhi Li, Visu Makam, Rafael Oliveira and Michael Walter.