ECE Seminar Speaker - Leonid Gurvits

A Poly-Time Deterministic Algorithm for Simply Exponential Approximation of the Permanent of PSD and Other Cool Quantum Things

Leonid GurvitsProfessor in the Computer Science Department at the City University of New York

Faculty Host:Alex Olshevsky

Refreshments at 10:45am

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 c^n approximation algorithm for the permanent of PSD matrices, where c is a universal constant (prior to this result not even randomized poly-time algorithm with (even) worst case simply exponential relative error was known); and e^n approximation algorithm for the quantum permanent of separable, aka non-entangled, bipartite density matrices. Our algorithm is based on a semidefinite 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 eigenvalue of certain n! × n! PSD matrices.

Bio:Leonid Gurvits was born in Soviet (aka Northern) Bukovina and lived there until the end of 1989. He started American life in 1990, in Brooklyn. He has worked in many areas and at many places, as academic as well industrial, but never at Wall Street. He spent the longest, and the most creative, stint at Los Alamos National Lab when it still was a great scientific institution. Since 2013, L.G. is a professor at the City College of New York. Leonid is the founder of the "hyperbolic polynomials approach" to combinatorics, geometry, counting and discrete math in general. One of his proofs has been recently included, as a new chapter, to the latest edition of "Proofs from the Book".