Optimization, Complexity and Invariant Theory

Abstract: The first two lectures will expand the panorama of research areas, motivations, problems and results in the scope of this workshop, highlighting many of the topics and lectures during this week. We will focus on one problem: the singularity of symbolic matrices (and its variations). We will take a (meandering) tour to discover how this problem arises independently in commutative and non-commutative algebra, quantum information theory, optimization, algebraic complexity theory, invariant theory, analysis, and advantages. Analyzing both requires tools from some of these diverse areas. We will focus on the analytic one: alternating minimization, and many of its consequences and extensions. We shall see how its template naturally aligns with geometric invariant theory, A key guiding aspect is seeking efficient algorithms for this singularity problem. This quest has exposed many of the connections above, and lead to two distinct efficient algorithms for it: one analytic and one algebraic, with somewhat complementary set of others. For each area, we shall take detours to highlight the context and guise in which this problem arises, and the connections it brings out between them. and how it was found to yield new algorithms and new structural results for problems in analysis, non-convex optimization, polyhedral combinatorics, operator theory, and back to invariant theory.