Optimization, Complexity and Invariant Theory

Abstract: The Quantum Permanent, the operator(explicitely) and polynomial(just for determinantal polynomials) Capacities were introduced by L.G. in 1999 on the DIMACS Matrix Scaling Workshop. The original motivation for the Quantum Permanent and the...

Abstract: Let P be a matrix property, e.g. having rank at most (or at least) k, being nilpotent, having no multiple eigenvalues, etc. We will survey some old and new results and problems on the maximal dimension of linear spaces of matrices having...

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