CCC'17 - Tutorial

In addition to the contributed talks, the program of CCC'17 includes a sequence of tutorials by Avi Wigderson on:

Operator scaling: theory, applications and connections

Date: Thursday 6th, Friday 7th, and Saturday 8th of July, 10:30-12:30.

Abstract:

The main problem of study in this tutorial is the singularity of symbolic matrices in non-commuting variables. Despite its esoteric sound, this problem has motivations and incarnations in surprisingly many areas of both CS (algebraic complexity and combinatorial optimization) and mathematics (non-commutative algebra, commutative invariant theory, quantum information theory and analysis).

The main result I will describe is a recent polynomial time algorithm for this problem via operator scaling, a quantum generalization of the classical matrix scaling problem. The bulk of the tutorial will be devoted to the analysis of this algorithm, which rests on certain developments in the mathematical areas listed above. To this end I'll introduce the necessary background in non-commutative algebra and invariant theory.

I will conclude with implications to optimization, complexity and analysis. The algorithm above efficiently solves a large class of non-convex problems, and a large class of exponential size linear programs. I will show a few applications and discuss potential to others. This algorithm has computational and structural implications to the family of Brascamb-Lieb inequalities in analysis, geometry and information theory, that I will exposit. Finally, together with a newer, very different algorithm, it suggests new approaches and questions regarding the classical PIT problem, and I'll explain these as well.

This tutorial is self-contained, and requires no special background.

Lecture schedule:

The first lecture will survey the landscape: problems, motivations, algorithms and the many areas of mathematics and CS which contribute and benefit from this study. The second lecture will give more details and proofs on algebraic aspects, and the third similarly on analytic aspects.

• Lecture 1 (July 6, 10:30-12:30): Video | Lecture notes
  I will define the problems of matrix and operator scalings and their origins and motivations. I will describe algorithms for solving both of them, explaining the similarities and differences in their performance analyses. I will then give brief introductions to the parts of Invariant Theory, Non-commutative fields and Quantum information theory that are used, and the notion of capacity, which is the key to the analysis which ties these areas together. I will hint at why this new algorithm has potential to solve new non-convex programs and exponentially large linear programs.

• Lecture 2 (July 7, 10:30-12:30): Video | Lecture notes
  I will explain the background in algebraic complexity motivating commutative and non-commutative PIT, introduce the commutative and non-commutative rank of symbolic matrices and their relation. This in particular will clarify why the operator scaling algorithm efficiently solves a large family of systems of quadratic equations. I will then survey basic definitions and problems in Invariant Theory, including the nullcone, invariant rings and their degrees, and then prove degree bounds on the group action we care about. I will discuss orbit problems and the connection to GCT (Geometric Complexity Theory).

• Lecture 3 (July 8, 10:30-12:30): Video | Lecture notes
  While PIT is the problem of proving algebraic identities, the analytic analog is proving inequalities. I will introduce, with many examples, the Brascamp-Lieb inequalities, a broad family which includes numerous famous inequalities throughout analysis, probability, information theory and geometry. I will discuss their rich structural theory and their basic computational problems. I will then describe an efficient algorithm for proving them. While it is derived from the operator scaling one, I will give a self-contained description naturally suggested from their structure theory. It should become clear why this algorithm efficiently solves large family of linear programs of exponential size, and I will give some examples.
  

Further references:

1. Ankit Garg, Leonid Gurvits, Rafael Oliveira, Avi Wigderson, Operator scaling: theory and applications, arXiv:1511.03730 [cs.CC], 2015.
2. Ankit Garg, Leonid Gurvits, Rafael Oliveira, Avi Wigderson, Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling, arXiv:1607.06711 [cs.CC], 2016.