Rutgers Discrete Mathematics Seminar

Title: Operator Scaling: Theory & Applications, and The Simplest Algorithm for the Linear Matroid Intersection Problem Ever Designed!

Speaker: Rafael Oliveira, Princeton University

Date: Monday, January 30, 2017 2:00 pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


In this talk we shall explore quantum operators, the operator scaling problem and its myriad incarnations in commutative and non-commutative algebra, computational complexity, optimization and quantum information theory. We will describe an efficient algorithm solving the operator scaling problem and all these related problems, and how its analysis combines ideas from all these areas. The problem these algorithms solve is non-convex, and we hope they will have many other applications.

As a combinatorial bonus, we will see the shortest algorithm for the linear matroid intersection problem ever designed!

Joint work with Ankit Garg, Leonid Gurvits and Avi Wigderson.