PreprintarXiv licencearXiv
Subexponential Approximation of the Permanent in Deterministic Polynomial Time
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 (O ((n(loglog n)2)/(log n)))=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.
Related
- A deterministic (1+ε)n approximation for the permanent of a nonnegative matrix
- A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs
- Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence
- A tight 1/3-approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem
- Beyond the Bethe Approximation of the Permanent
BibTeX
@misc{kudria2026subexponential,
title = {{Subexponential Approximation of the Permanent in Deterministic Polynomial Time}},
author = {Sergei Kudria and Jason Luo and Mahbod Majid},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10516},
eprint = {2609.10516},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10516},
}
RIS
TY - UNPB
TI - Subexponential Approximation of the Permanent in Deterministic Polynomial Time
AU - Sergei Kudria
AU - Jason Luo
AU - Mahbod Majid
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.10516
UR - https://arxiv.org/abs/2609.10516
AB - 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 (O ((n(loglog n)^2)/(log n)))=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.
ER -