Seminars

Jun
08
2018

Optimization, Complexity and Invariant Theory

Capacities, Hyperbolicity, Submodularity and all the jazz...
11:15am

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

Jun
08
2018

Optimization, Complexity and Invariant Theory

Combinatorial methods for PIT (and ranks of matrix spaces)
9:30am

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

Jun
07
2018

Optimization, Complexity and Invariant Theory

Solution to the Paulsen problem (via operator scaling)
Lap Chi Lau
3:45pm

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

Jun
07
2018

Optimization, Complexity and Invariant Theory

Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Yuanzhi Li
2:00pm

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

Jun
07
2018

Optimization, Complexity and Invariant Theory

An Introduction to Geodesic Convexity
Nisheeth Vishnoi
11:15am

Abstract: Sometimes, functions that are non-convex in the Euclidean space turn out to be convex if one introduces a suitable metric on the space and redefines convexity with respect to the straight lines ("geodesics") induced by the metric. Such a...

Jun
07
2018

Optimization, Complexity and Invariant Theory

The dynamics of regularized flows on convex bodies
9:30am

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

Jun
06
2018

Optimization, Complexity and Invariant Theory

Geometric complexity theory (GCT): Algorithmic challenges in invariant theory
Ketan D. Mulmuley
3:45pm

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

Jun
06
2018

Optimization, Complexity and Invariant Theory

Algorithmic invariant theory
Visu Makam
2:00pm

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

Jun
06
2018

Optimization, Complexity and Invariant Theory

Some PIT problems in the light of the non-communtative rank algorithm
Gábor Ivanyos
11:15am

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

Jun
06
2018

Optimization, Complexity and Invariant Theory

An algebraic algorithm for non-commutative rank over any field
K.V. Subrahmanyam
9:30am

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