Theory Seminar - On the Permanent of Positive Semidefinite Matrices

Title: On the Permanent of Positive Semidefinite Matrices 

Abstract: Computing the permanent of non-negative matrices has received a lot of attention over the past two decades. The beautiful result of Jerrum-Sinclair-Vigoda gives a fully polynomial-time approximation scheme for the problem and the proof of Van der Waerden conjecture gives exponential deterministic approximations for it.

On the other hand, we know very little about the computation of the permanent of positive semidefinite matrices. I will talk about various open problems in this area and present our result, which is the first simply exponential approximation for the problem. 

Joint work with N. Anari, L. Gurvits, and S. Oveis Gharan.