Optimization, Complexity and Invariant Theory

Abstract: Scaling problems have a rich and diverse history, and thereby have found numerous applications in several fields of science and engineering. For instance, the matrix scaling problem has had applications ranging from theoretical computer science to telephone forecasting, economics, statistics, optimization, among many other fields. Recently, a generalization of matrix scaling known as operator scaling has found applications in non-commutative algebra, invariant theory, combinatorics and algebraic complexity; and a further generalization (tensor scaling) has found more applications in quantum information theory, geometric complexity theory and invariant theory. In this talk, we will describe in detail the scaling problems mentioned above, showing how alternate minimization algorithms naturally arise in this setting, and we shall present a general framework to rigorously analyze such algorithms. This framework will make use of concepts from invariant theory and representation theory described in the introductory lectures.