Computational Complexity Conference

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.


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.

Reference material:

Organized by:

Computational Complexity Foundation Inc.

In Cooperation with:


Sponsored by:

Microsoft Research

University of Latvia