Approximation threshold for positive-semidefinite permanents

How well can the permanent of an n×n Hermitian positive semidefinite matrix be approximated deterministically in polynomial time? The target is an exponential factor e^((γ+ε)n) for every ε>0, matching the cited hardness exponent up to lower-order terms.

Why it matters and what counts as progress

Why it matters: Closing the exponent gap would align a convex approximation guarantee with the known computational obstruction, assuming P≠NP.

What counts as progress: A polynomial-time approximation at the γ exponent with proved two-sided bounds, or a stronger hardness result under explicitly stated complexity assumptions.

How the problem developed

2017 · Algorithm [1]
Nima Anari, Leonid Gurvits, Shayan Oveis Gharan and Amin Saberi Gave a deterministic polynomial-time e^(1+γ)n approximation for permanents of positive-semidefinite matrices.
16 Apr 2024 · Partial result [2]
Farzam Ebrahimnejad, Ansh Nagda and Shayan Oveis Gharan Improved the deterministic upper bound to e^(0.9999+γ)n and proved NP-hardness below e^(γ−ε)n.
21 May 2026 · Reported claim [3]
Nima Anari and Farzam Ebrahimnejad, with GPT-5.5 Pro Extended Claimed a deterministic polynomial-time e^(γ+ε)n approximation for every ε>0, meeting the known exponential hardness scale up to the ε term.

AI contribution

Optimal e^((γ+o(1))n)-Approximation of the Permanent of Positive Semidefinite Matrices

Nima Anari, Farzam Ebrahimnejad

For an n×n Hermitian positive semidefinite matrix A, an entropy-corrected concave Gram-factor relaxation P̂ satisfies e^(−γn)P̂≤per(A)≤P̂ and gives a deterministic polynomial-time e^((γ+ε)n)-approximation for every ε>0. The exponent is optimal up to lower-order terms under the cited NP-hardness, assuming P≠NP.

AI involvementAI-autonomous

ImportanceNotable

Technical verificationFormal (human)

Human understandingFull