Previous Conferences & Workshops

Abstract: The Paulsen problem is a basic open problem in operator theory. We define a continuous version of the operator scaling algorithm to solve this problem. A key step is to show that the continuous operator scaling algorithm converges faster...

Abstract: We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and...

Abstract: It has long been understood that endowing a convex body with a Riemannian metric derived from the Hessian of a convex function can be instrumental in controlling the convergence of flows (local algorithms) toward equilibrium. This is...

Abstract:This talk will describe some algorithmic challenges, relevant to this workshop, that arise in the context of the geometric complexity theory (GCT) approach to the fundamental lower bound and polynomial identity testing problems of...

Abstract: Many important problems in computational complexity can be rewritten in the language of invariant theory. Famous examples include the graph isomorphism problem, and the GCT approach to P vs NP. The focus of this talk will be to illustrate...

Abstract: We show some results from (classical commutative) Polynomial Identity Testing in which the results or the technical ingredients of the noncommutative rank algorithm presented in the preceding talk play an important role. These include...

In 1967, J. Edmonds introduced the problem of computing the rank over the rational function field of an $n \times n$ matrix $M_1x_1 + \dotsb + M_mx_m$ whose entries are homogeneous linear polynomials in commuting variables $x_1, x_2, \dotsc, x_m$...

Abstract: We wish to understand when a tensor s can be transformed into a tensor t by application of linear maps to its tensor legs (we then say s restricts to t). In the language of restrictions, the rank of a tensor t is given by the minimal size...

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...

Abstract: In this second lecture, we will continue our gentle introduction. We will discuss some of the underlying geometry and introduce the associated moment polytopes. These are a rich class of convex polytopes that arise naturally in a variety...