Optimization, Complexity and Invariant Theory

Abstract: An invariant is a function that remains unchanged under certain transformations. If an invariant has different values on two objects, then we have an easy proof that one object cannot be transformed into the other. In Invariant Theory one studies invariants that are polynomial where the transformations are symmetries coming from a group representation. Some applications are graph theory, coding theory, material science and computer vision. If a group acts on an n-dimensional space by linear transformations, then a invariant is a polynomial function on the space that is constant on each orbit. Invariants are useful for determining whether two vectors lie in the same orbit. Products and sums and differences of invariants are again invariant, so the invariants form a ring. This invariant ring is the main object of study in Invariant Theory. A breakthrough was achieved by David Hilbert in the late 1800s who showed that (under some assumptions) there exist finitely many fundamental invariants such that every invariant can be expressed in these fundamental invariants. We will discuss upper bounds for the degrees of the fundamental invariants. Examples that will be discussed include invariants of the symmetric group, invariants for binary forms and matrix invariants.