Subexponential Approximation of the Permanent in Deterministic Polynomial Time

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 order $n$, the approximation factor is $$\exp \text{\hspace{0.17em}⁣}\left(O\text{\hspace{0.17em}⁣}\left(\frac{n(\log \log n{)}^2}{\log n}\right)\right)=\exp (o(n))\mathrm{.}$$ All previously known deterministic polynomial time guarantees for unrestricted inputs had approximation factors $\exp (\mathrm{\Omega }(n))$. Our proof uses convex optimization to tighten an upper bound on the permanent. The bound is based on weighted sums over all matchings in a bipartite graph representing the matrix, and correlations between unmatched vertices control its error. We approximate these sums deterministically using correlation decay and a bound on the effect of vertex deletion.