Invariant theory is a fundamental subject in mathematics, and is potentially applicable whenever there is symmetry at hand (group actions). In recent years, new problems and conjectures inspired by complexity have come to light. In this talk, I will describe some of these new problems, and discuss some positive and negative results regarding them.