Decision and Control Laboratory and the Illinois Institute for Data Science and Dynamical Systems || Professor Leonid Gurvits|| A Poly-time DETERMINISTIC Algorithm for Simply Exponential Approximation of the Permanent of PSD Matrices and Other Cool Quant

Bio: Leonid Gurvits is a Professor of Computer Science at the City College of New York. He is known for fundamental contributions to the theory of nonholonomic motion planning, computational complexity, and classical and quantum computation. His proof of van der Waerden’s permanent conjecture has been included as a chapter in the sixth edition of Martin Aigner and Günter Ziegler’s “Proofs from THE BOOK.”

Abstract:

I will first explain the importance of the permanent of PSD matrices in Quantum Linear
Optics, and put it into more general concept of so called quantum permanent of bipartite
density matrices.
     In this talk I will show how to get a cn approximation algorithm for the permanent of
PSD matrices, where c is a universal constant (prior to this result not even random-
ized poly-time algorithm with (even) worst case simply exponential relative
error was known); and en approximation algorithm for the quantum permanent of sep-
arable, aka non-entangled, bipartite density matrices.

        Our algorithm is based on a semide nite program with a convex nonlinear objective.
Our proof of its correctness is essentially a New Van Der Waerden Like Lower Bound:
What is the smallest value of the permanent of projectors on images of n n
correlation matrices?
       If time permits, I will talk about how our result can \save" the recently refuted
permanent-on-top conjecture as well as its application to approximating the largest eigen-
value of certain n! n! PSD matrices.
Based on the joint work with Nima Anari, Shayan Oveis Gharan, Amin Saberi.