Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices
Presenter
April 13, 2018
Abstract
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.