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 non-commutative 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 non-communtative 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 information-theoretic flavor of the problem is apparent and was heavily used by Strassen in conjunction with the discovery of algebraic structures (his spectral theorem).
Identifying k-leg-tensors 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 n-dimensional 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 Hilbert-Mumford criterion and the Kempf-Ness theorem, which provide an intriguing extension of linear programming duality (or Farkas’ lemma) to non-commutative 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 log-concave 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 poly-time 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 poly-time 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 non-communtative 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 long-standing 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 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 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 left-right 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 Allen-Zhu, 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 semi-invariants 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 min-max 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 non-commutative 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 non-commutative 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 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 function is called "geodesically convex" and, when a function has this property and how to optimize over it, is not well-understood. This talk will introduce geodesic convexity and show that the problem of computing the Brascamp-Lieb 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 Hilbert-Mumford criterion and the Kempf-Ness theorem, which provide an intriguing extension of linear programming duality (or Farkas’ lemma) to non-commutative 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 non-commutative 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, non-convex optimization, polyhedral combinatorics, operator theory, and back to invariant theory.