Polynomial Time Algorithms To Approximate Permanents And Mixed Discriminants Within A Simply Exponential Factor

We present real, complex, and quaternionic versions of a simple randomized polynomial time algorithm to approximate the permanent of a non-negative matrix and, more generally, the mixed discriminant of positive semidefinite matrices. The algorithm provides an unbiased estimator, which, with high probability, approximates the true value within a factor of O(c n ), where n is the size of the matrix (matrices) and where c 0:28 for the real version, c 0:56 for the complex version and c 0:76 for the quaternionic version. We discuss possible extensions of our method as well as applications of mixed discriminants to problems of combinatorial counting