Agenda
The first 6 lectures, on Monday and on Tuesday morning, are designed as introductory lectures, partly to facilitate later lectures. They assume no special background. More high level lectures and surveys are spread throughout the program.
Lectures will take place in Wolfensohn Hall on Monday through Thursday. On Friday, talks and open problem sessions will be in Simonyi 101.
Lunches will be served in Simons Hall  Lunch tickets will be sold daily for $15(cash only) at the registration desk.
Monday, June 4
9:00 a.m. – 9:20 a.m.  Registration open 
9:20 a.m. – 9:30 a.m.  Opening remarks 
9:30 a.m. – 10:45 a.m. 
Motivations, connections and scope of the workshop 
10:45 a.m. – 11:15 a.m.  Coffee break 
11:15 a.m. – 12:30 p.m. 
Motivations, connections and scope of the workshop 
12:45 p.m. – 2:00 p.m.  Lunch break 
2:00 p.m. – 3:15 p.m. 
A gentle introduction to group representation theory 
3:15 p.m. – 3:45 p.m.  Coffee break 
3:45 p.m. – 5:00 p.m. 
An introduction to Invariant Theory 
Tuesday, June 5
8:30 a.m. – 9:30 a.m.  Morning coffee and tea 
9:00 a.m. – 9:30 a.m.  Registration open 
9:30 a.m. – 10:45 a.m. 
Introduction to geometric invariant theory 1: Noncommutative duality 
10:45 a.m. – 11:15 a.m.  Coffee break 
11:15 a.m. – 12:30 p.m.  Introduction to geometric invariant theory 2: Moment polytopes Michael Walter  University of Amsterdam Video Slides 
12:45 p.m. – 2:00 p.m.  Lunch break 
2:00 p.m. – 3:15 p.m. 
Alternate minimization algorithms for scaling problems, and their analysis 
3:15 p.m. – 3:45 p.m.  Coffee break 
3:45 p.m. – 5:00 p.m. 
Tensors: rank, entropy and entanglement 
Wednesday, June 6
8:30 a.m. – 9:30 a.m.  Morning coffee and tea 
9:00 a.m. – 9:30 a.m.  Registration open 
9:30 a.m. – 10:45 a.m. 
An algebraic algorithm for noncommutative rank over any field 
10:45 a.m. – 11:15 a.m.  Coffee break 
11:15 a.m. – 12:30 p.m. 
Some PIT problems in the light of the noncommuntative rank algorithm 
12:45 p.m. – 2:00 p.m.  Lunch break 
2:00 p.m. – 3:15 p.m.  Algorithmic invariant theory Visu Makam  University of Michigan Video 
3:15 p.m. – 3:45 p.m.  Coffee break 
3:45 p.m. – 5:00 p.m. 
Geometric complexity theory (GCT): Algorithmic challenges in invariant theory 
5:45 p.m. – 7:45 p.m.  Reception in front of Wolfensohn Hall 
Thursday, June 7
8:30 a.m. – 9:30 a.m.  Morning coffee and tea 
9:00 a.m. – 9:30 a.m.  Registration open 
9:30 a.m. – 10:45 a.m. 
The dynamics of regularized flows on convex bodies 
10:45 a.m. – 11:15 a.m.  Coffee break 
11:15 a.m. – 12:30 p.m.  An Introduction to Geodesic Convexity Nisheeth Vishnoi  EPFL Video Slides 
12:45 p.m. – 2:00 p.m.  Lunch break 
2:00 p.m. – 3:15 p.m.  Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing Yuanzhi Li  Princeton University Video Slides 
3:15 p.m. – 3:45 p.m.  Coffee break 
3:45 p.m. – 5:00 p.m. 
Solution to the Paulsen problem (via operator scaling) 
Friday, June 8 (note the slightly different schedule) Talks will be held in Simonyi 101
8:30 a.m. – 9:30 a.m.  Morning coffee and tea 
8:30 a.m. – 9:00 a.m.  Registration open 
9:00 a.m. – 10:15 a.m. 
Combinatorial methods for PIT (and ranks of matrix spaces) 
10:15 a.m. – 10:30 a.m.  Coffee break 
10:30 a.m. – 11:45 p.m.  Capacities, Hyperbolicity, Submodularity and all the jazz... Leonid Gurvits  The City College of New York Video 
11:45 p.m. – 1:00 p.m.  Lunch break 
1:00 p.m. – 2:15 p.m.  New directions and Open problems 
2:15 p.m. – 2:45 p.m.  Break 
2:45 p.m. – 4:00 p.m.  New directions and Open problems 
The workshop is free of charge and attendees must register to attend the workshop.
Invited Speakers
Below is a summary of the speaker talks that will take place during the workshop.
Peter Buergisser  Technical University of Berlin
Monday from 2:00 p.m.  3:15 p.m.
A gentle introduction to group representation theory
Abstract: Symmetries are a main source of unifying principles in mathematics and physics and groups are the appropriate mathematical concept for describing symmetries. Representation theory studies linear transformations in the presence of symmetries and, e.g., plays a major role in quantum mechanics. In computer science, group symmetries are behind several fast algorithms, like the Fast Fourier transform, fast arithmetic of numbers and polynomials, matrix multiplication, construction of expanders etc. Naturally, the fundamental graph isomorphism problem is intimately connected to group theory. Geometric complexity theory postulates that symmetries and representation theory will play a key role in unveiling the mysteries of computational complexity.
The talk is planned as a gentle introduction to representation theory, explaining the motivations, the key concepts and some of the key theorems. The main focus will be on the representations of the tori (C^*)^n and the general linear groups (with some explanations on the connections with the symmetric groups). In particular, we aim at explaining the basics of the powerful theory of highest weight vectors, which leads to a concrete description of representations, and which is the starting point of many investigations in geometric complexity theory and quantum information theory.
Matthias Christandl  University of Copenhagen
Tuesday from 3:45 p.m.  5:00 p.m.
Tensors: rank, entropy and entanglement
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 of a diagonal tensor restricting to t. The study of rank and restrictions are motivated by algebraic complexity theory, where the rank corresponds to the computational complexity of a bilinear map (e.g. matrix multiplication) which then is viewed as a tensor with three legs.
Interestingly, some important open problems can be formulated in terms of asymptotic properties of restriction, among them the exponent of matrix multiplication. Following the seminal work of Volker Strassen, we will therefore study whether for large n the (n+o(n))'th tensor power of s can be restricted to the n'th tensor power of t. The informationtheoretic flavor of the problem is apparent and was heavily used by Strassen in conjunction with the discovery of algebraic structures (his spectral theorem).
Identifying klegtensors with states of quantum systems of k particles allows us to bring tools and ideas from quantum information theory to the table, among them entanglement polytopes and quantum entropy. I will use these to construct a family of functionals  the quantum functionals  that can serve as obstructions to asymptotic restrictions. The functionals are the first of their kind applicable to all tensors, thereby solving a problem by Strassen from 1986.
Harm Derksen  University of Michigan
Monday from 3:45 p.m.  5:00 p.m.
An introduction to Invariant Theory
Abstract: An invariant is a function that remains unchanged under certain transformations. If an invariant has different values on two objects, then we have an easy proof that one object cannot be transformed into the other. In Invariant Theory one studies invariants that are polynomial where the transformations are symmetries coming from a group representation. Some applications are graph theory, coding theory, material science and computer vision.
If a group acts on an ndimensional space by linear transformations, then a invariant is a polynomial function on the space that is constant on each orbit. Invariants are useful for determining whether two vectors lie in the same orbit. Products and sums and differences of invariants are again invariant, so the invariants form a ring. This invariant ring is the main object of study in Invariant Theory. A breakthrough was achieved by David Hilbert in the late 1800's who showed that (under some assumptions) there exist finitely many fundamental invariants such that every invariant can be expressed in these fundamental invariants. We will discuss upper bounds for the degrees of the fundamental invariants. Examples that will be discussed include invariants of the symmetric group, invariants for binary forms and matrix invariants.
Ankit Garg  Microsoft Research New England
Tuesday from 9:30 a.m.  10:45 a.m.
Introduction to geometric invariant theory 1: Noncommutative duality
Abstract: We will give a gentle introduction to geometric invariant theory, which provides geometric and analytic tools to study problems in invariant theory. We will explain the basic tools and concepts and give many motivating examples. In the first lecture, we will introduce moment maps and discuss the HilbertMumford criterion and the KempfNess theorem, which provide an intriguing extension of linear programming duality (or Farkas’ lemma) to noncommutative group actions.
In the 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 of applications, such as the Newton polytopes of polynomials, eigenvalue problems in linear algebra, and the study of entanglement in quantum information theory, giving rise to many interesting computational problems.
Introduction to geometric invariant theory 2: Moment polytopes
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 of applications, such as the Newton polytopes of polynomials, eigenvalue problems in linear algebra, and the study of entanglement in quantum information theory, giving rise to many interesting computational problems.
Leonid Gurvits  CCNY
Friday from 10:30 a.m.  11:45 a.m.
Capacities, Hyperbolicity, Submodularity and all the jazz...
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 Operator Capacity was the Bapat's conjecture, a generalization on the Van Der Waerden conjecture to mixed discriminants. The polynomial capacity first showed up as a natural convex relaxation for the mixed discriminant.
These capacities and their generalizations have grown up recently, rather surprisingly to the author, into powerful tools as for algorithms as well for proofs. The most spectacular applications of Operator Capacity is in decision problems, the polynomial capacity is the main engine behind amazingly transparent proofs of hard combinatorial and geometric lower bounds involving hyperbolic and, more generally, strongly logconcave polynomials.
I will describe in this talk much less known polynomial time algorithms for several decision problems in the hyperbolic framework. They are possible because of hyperbolic Hall's theorem, a hidden submodularity and other cool things.
Time permitting, I will describe the recent deterministic polytime algorithm for the Quantum permanent of separable bipartite states, where the operator and polynomial capacities meet and need each other.
Even more conditionally, I will describe the recent deterministic polytime algorithm, e.g. a convex relaxation, for the permanent of PSD matrices, where neither Operator Capacity nor Hyperbolicity help, so far...
Gábor Ivanyos  Research Institute of Computer Science and Control of the Hung. Acad. Sci., Budapest, Hungary
Wednesday from 11:15 a.m.  12:30 p.m.
Some PIT problems in the light of the noncommuntative rank algorithm
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:
 computing nontrivial common block triangularizations of several matrices with an application in multivariate cruptography,
 some further problems from computational representation theory of finite groups and algebras,
 spaces spanned by rank one matrices, and
 a recent result of Bläser, Jindal and Pandey on approximating the commutative rank.
We are also planning to mention some further special instances of PIT that are perhaps not hopeless to be derandomized or to be shown hard.
Lap Chi Lau  University of Waterloo
Thursday from 3:45 p.m.  5:00 p.m.
The Paulsen problem, continuous operator scaling, and smoothed analysis
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 in a perturbed input. To this end, we develop some new techniques in lower bounding the operator capacity, a concept introduced by Gurvits to analyze the operator scaling algorithm.
Joint work with Tsz Chiu Kwok, Yin Tat Lee, and Akshay Ramachandran.
James Lee  University of Washington
Thursday 9:30 a.m.  10:45 a.m.
The dynamics of regularized flows on convex bodies
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 because such geometries come equipped with a natural Lyapunov function (the associated Bregman divergence). I will discuss the basic theory of these dynamics and how they can be used to pursue a moving target through a convex body. This leads to the resolution of some longstanding open problems in competitive analysis.
The talk is based on joint works with S. Bubeck, M. Cohen, Y. T. Lee, and A. Madry.
Yuanzhu Li  Princeton University
Thursday from 2:00 p.m.  3:15 p.m.
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Abstract: We propose a new secondorder 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 logarithmic in the error. This is an exponential improvement over previous algorithms which were analyzed in the usual Euclidean, ``commutative'' metric (for which the above problem is not convex). As a consequence, we solve the equivalence problem for the leftright group action underlying the operator scaling problem. We give a deterministic polynomial time algorithm for a new class of Polynomial Identity Testing (PIT) problems, which was the original motivation for studying operator scaling.
This is joint work with Zeyuan AllenZhu, Ankit Garg, Rafael Oliveira and Avi Wigderson.
Visu Makam  University of Michigan
Wednesday from 2:00 p.m.  3:15 p.m.
Algorithmic invariant theory
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 the rich interaction between algebra and algorithms in invariant theory. We will work closely with the examples of matrix invariants and semiinvariants where the algebraic and algorithmic aspects aid each other's progress.
Roy Meshulam  Technion
Friday from 9:00 a.m.  10:15 a.m.
Combinatorial methods for PIT (and ranks of matrix spaces)
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 property P. In particular, we'll discuss the following topics:

Spaces of matrices of rank at most k: Flanders type theorems and their connections with matching theory.

Bounded rank subspaces of the exterior algebra and weak matchings in hypergraphs.

The Edmonds and Lovasz minmax theorems, and the search for efficient deterministic algorithms for PIT.
 Spaces of matrices of rank at least k: The cases of algebraically closed vs. finite fields.

Spaces of real nonsingular matrices: Clifford algebras and topological upper bounds.

Spaces of nilpotent elements: Gerstenhaber type theorems and their Lie algebra extensions.
Ketan D. Mulmuley  University of Chicago
Wednesday from 3:45 p.m.  5:00 p.m.
Geometric complexity theory (GCT): Algorithmic challenges in invariant theory
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 complexity theory.
No prior knowledge of GCT will be assumed.
Rafael Oliveira  University of Toronto
Tuesday from 2:00 p.m.  3:15 p.m.
Alternate minimization algorithms for scaling problems, and their analysis
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 science to telephone forecasting, economics, statistics, optimization, among many other fields. Recently, a generalization of matrix scaling known as operator scaling has found applications in noncommutative algebra, invariant theory, combinatorics and algebraic complexity; and a further generalization (tensor scaling) has found more applications in quantum information theory, geometric complexity theory and invariant theory.
In this talk, we will describe in detail the scaling problems mentioned above, showing how alternate minimization algorithms naturally arise in this setting, and we shall present a general framework to rigorously analyze such algorithms. This framework will make use of concepts from invariant theory and representation theory described in the introductory lectures.
K Venkata Subrahmanyam  Chennai Mathematical Institute, Chennai, India
Wednesday from 9:30 a.m.  10:45 a.m.
An algebraic algorithm for noncommutative rank over any field
Nisheeth Vishnoi  EPFL
Thursday from 11:15 a.m.  12:30 p.m.
An Introduction to Geodesic Convexity
Abstract: Sometimes, functions that are nonconvex 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 function is called "geodesically convex" and, when a function has this property and how to optimize over it, is not wellunderstood. This talk will introduce geodesic convexity and show that the problem of computing the BrascampLieb constant has a succinct geodesically convex formulation.
Michael Walter  University of Amsterdam
Tuesday from 11:15 a.m.  12:30 p.m.
Introduction to geometric invariant theory 1: Noncommutative duality
Abstract: We will give a gentle introduction to geometric invariant theory, which provides geometric and analytic tools to study problems in invariant theory. We will explain the basic tools and concepts and give many motivating examples. In the first lecture, we will introduce moment maps and discuss the HilbertMumford criterion and the KempfNess theorem, which provide an intriguing extension of linear programming duality (or Farkas’ lemma) to noncommutative group actions.
In the 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 of applications, such as the Newton polytopes of polynomials, eigenvalue problems in linear algebra, and the study of entanglement in quantum information theory, giving rise to many interesting computational problems.
Introduction to geometric invariant theory 2: Moment polytopes
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 of applications, such as the Newton polytopes of polynomials, eigenvalue problems in linear algebra, and the study of entanglement in quantum information theory, giving rise to many interesting computational problems.
Avi Wigderson  Institute for Advanced Study
Monday from 9:30 a.m.  10:45 a.m. and 11:15 a.m.  12:30 p.m.
Motivations, connections and scope of the workshop
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 noncommutative algebra, quantum information theory, optimization, algebraic complexity theory, invariant theory, analysis, and 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.
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 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, and how it was found to yield new algorithms and new structural results for problems in analysis, nonconvex optimization, polyhedral combinatorics, operator theory, and back to invariant theory.