{"id":"arxiv/2609.10516","url":"https://arxiv.org/abs/2609.10516","tags":["cs.DS","cs.CC","math.CO"],"score":0,"title":"Subexponential Approximation of the Permanent in Deterministic Polynomial Time","domain":"cs.DS","source":"arxiv","authors":["Sergei Kudria","Jason Luo","Mahbod Majid"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-09","reactions":{}}