# 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

https://www.ias.edu/math/files/avi/kv-ias-abstract.pdf