Subexponential Approximation of the Permanent in Deterministic Polynomial Time

Sergei Kudria, Jason Luo, Mahbod Majid

We give the first deterministic polynomial time algorithm that approximates the permanent of arbitrary nonnegative rational matrices within a subexponential factor. For a matrix of…