BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices Saberi, Amin

Description

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.

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International