Deterministic algorithm improves permanent matrix approximation accuracy
Subexponential Approximation of the Permanent in Deterministic Polynomial Time
Data Structures and AlgorithmsComputational Complexity
Summary
Calculating the permanent of a matrix is important in math and computer science but is very hard to do exactly. This paper presents a new algorithm that can approximate the permanent for any nonnegative matrix much more closely than before using a fast, predictable method. The key idea is to use clever math tools to better estimate important sums related to the matrix, improving previous methods that had much larger errors. This makes it possible to get a good approximation in a reasonable amount of time for bigger problems than before.
What this means in practice
- •For algorithm engineers: Design faster, reliable algorithms for matrix computations where exact permanent is infeasible but better approximations matter.
- •For cryptography developers: Improve analysis tools for cryptographic schemes related to counting perfect matchings or permanents by using tighter approximation bounds.
A theory result. No direct application yet.
Authors
Sergei Kudria, Jason Luo, Mahbod Majid
Abstract
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\!\left(O\!\left(\frac{n(\log\log n)^2}{\log n}\right)\right)=\exp(o(n)). \] All previously known deterministic polynomial time guarantees for unrestricted inputs had approximation factors $\exp(Ω(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.