Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices

Amin Saberi
Stanford University

I will present a deterministic polynomial time c^n approximation algorithm for the permanent of positive semidefinite matrices where c ~ 4.84. This is through a natural convex programming relaxation and proving a PSD variation of the Van der Waerden's theorem.

Joint work with Nima Anari, Shayan Oveis Gharan, and Leonid Gurvitz.

Back to Workshop I: Expected Characteristic Polynomial Techniques and Applications