Abstract
Despite superficial similarities with the determinant, the permanent is #P-hard to compute, even for {0,1}-matrices. A long line of work has focused on designing approximation algorithms for the permanent of matrices with nonnegative entries, culminating with an FPRAS due to Jerrum, Sinclair, and Vigoda.
The permanent has been known to also be nonnegative for another class of matrices, namely positive semidefinite (PSD) 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.
Our algorithm is based on a semidefinite program with a convex nonlinear objective. We show that the input matrix can be sandwiched between a diagonal matrix and a rank-1 matrix whose permanents differ by at most a factor of c^n. To obtain the lower bound matrix we use a randomized rounding technique based on projections onto complex gaussian vectors.
If time permits, I will talk about the implications of our result for the recently refuted permanent-on-top conjecture as well as some open problems.
Joint work with Leonid Gurvits, Shayan Oveis Gharan, Amin Saberi.