Videos

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.