Optimal e^((γ+o(1))n)-Approximation of the Permanent of Positive Semidefinite Matrices
Pith reviewed 2026-05-22 03:15 UTC · model grok-4.3
The pith
A concave optimization yields a deterministic e^{(γ + o(1))n}-approximation for the permanent of positive semidefinite matrices.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The authors establish the exact sandwich e^{-γ n} hat P(A) ≤ per(A) ≤ hat P(A) for the defined hat P(A) = exp(Φ(V)), with Φ(V) being the maximum over positive definite matrices X of the sum of logs of quadratic forms plus log det X minus trace X plus dimension d. The proof applies an entropy argument to the standard Wick integral formula for the permanent, where the loss factor per entry is exactly γ because the expected value of the logarithm of a random variable distributed as Exp(1) is -γ. This yields the optimal deterministic polynomial-time approximation ratio of e^{(γ + o(1))n} when paired with prior hardness.
What carries the argument
The concave program Φ(V) = max_{X ≻ 0} {∑ log(v_i† X v_i) + log det(X) - tr(X) + d} whose exponential gives the upper bound hat P(A) on the permanent.
If this is right
- Deterministic polynomial-time algorithms can approximate the permanent of PSD matrices to within e^{(γ + ε)n} for arbitrary ε > 0.
- The approximation ratio e^{(γ + o(1))n} is tight for deterministic polynomial-time methods under the assumption that P ≠ NP.
- The entropy method applied to the Wick formula gives a precise constant γ loss without additional factors in the exponent.
Where Pith is reading between the lines
- If the sandwich is tight for some families of matrices, it would imply that the approximation is sharp even for specific instances.
- The technique of using entropy on integral representations may apply to approximating other algebraic quantities like determinants or Hafnians in related settings.
- Implementing the concave maximization numerically for moderate-sized matrices could provide practical approximation algorithms beyond the theoretical guarantee.
Load-bearing premise
The load-bearing premise is that the entropy argument on the Wick integral incurs a multiplicative loss of exactly e^{-γ} per dimension due to the expectation of log T for T exponential with mean one, with no further losses from discretization or approximation in the maximization.
What would settle it
Solve the concave program numerically for a chosen 5-by-5 positive semidefinite matrix with no zero diagonal to get hat P(A), compute the exact permanent via enumeration or Ryser's formula, and verify if per(A) / hat P(A) >= e^{-γ * 5}; any matrix where this ratio is smaller would falsify the claimed lower bound.
read the original abstract
We determine, up to lower-order terms in the exponent, the best possible deterministic polynomial-time approximation ratio for the permanent of a Hermitian positive semidefinite matrix. If $A\succeq 0$ has no zero diagonal entry, $d=\operatorname{rank}(A)$, $A=VV^\dagger$ with $V\in\mathbb{C}^{n\times d}$ full column rank, and $v_1,\ldots,v_n$ are the rows of $V$, define \[ \Phi(V)=\max_{X\succ 0} \left\{\sum_{i=1}^n \log(v_i^\dagger Xv_i)+\log\det X-\operatorname{tr} X+d\right\}, \qquad \widehat P(A)=e^{\Phi(V)}. \] We prove the exact sandwich \[ e^{-\gamma n}\widehat P(A)\le \operatorname{per}(A)\le \widehat P(A). \] Here $\gamma$ is the Euler--Mascheroni constant. Since the maximization is concave, this gives a deterministic polynomial-time $e^{(\gamma+\varepsilon)n}$-approximation for every $\varepsilon>0$. Combined with the previous $e^{(\gamma-\varepsilon)n}$-hardness of approximation for positive semidefinite permanents, this resolves the optimal exponential approximation ratio for deterministic polynomial-time algorithms as $e^{(\gamma+o(1))n}$, assuming $\mathrm{P}\ne\mathrm{NP}$. The proof is an entropy argument applied to the standard Wick integral formula for $\operatorname{per}(A)$; the loss is exactly $\gamma$ per factor because $\mathbb{E}[\log T]=-\gamma$ for $T\sim\operatorname{Exp}(1)$. The result was obtained through interactions with GPT 5.5 Pro Extended: the first author's interaction was one-shot, while the second author's was a separate multi-turn interaction with high-level guidance. Both authors verified the theorem and proof. Codex was used to assemble and typeset the manuscript.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript claims to determine the optimal deterministic polynomial-time approximation ratio for the permanent of Hermitian positive semidefinite matrices as e^{(γ + o(1))n}. It defines Φ(V) as the maximum over X ≻ 0 of ∑ log(v_i† X v_i) + log det X - tr X + d for V with rows v_i, setswidehat P(A) = e^{Φ(V)}, and proves the exact sandwich e^{-γ n} widehat P(A) ≤ per(A) ≤ widehat P(A) via an entropy argument on the Wick integral formula, with the γ loss per factor coming from E[log T] = -γ for T ~ Exp(1). The maximization being concave yields a poly-time e^{(γ + ε)n}-approximation for any ε > 0, which is optimal given prior hardness assuming P ≠ NP.
Significance. If the sandwich holds, the result is significant: it pins down the precise exponential approximation factor for PSD permanents, closing the gap to the known e^{(γ - ε)n} hardness threshold up to o(n) terms. The variational characterization is efficiently computable by convex optimization, and the entropy argument provides a clean probabilistic explanation for the constant γ. The manuscript also notes machine-assisted derivation with human verification, which is a positive disclosure for reproducibility.
major comments (1)
- [Abstract, sandwich inequality] Abstract, sandwich inequality: the entropy argument with E[log T] = -γ and Jensen on the concave log yields the lower bound e^{-γ n} widehat P(A) ≤ per(A) via linearity of expectation on ∑ log T_i. However, the same marginals do not imply E[∏ T_i] ≤ 1 for the upper bound per(A) ≤ widehat P(A); when the rows v_i are linearly dependent the joint law of the |v_i^* z|^2 terms can make the expectation exceed 1. The manuscript must therefore supply a distinct Wick-derived inequality or show that the parameterized family achieves the full Donsker–Varadhan supremum. Please cite the specific lemma or subsection establishing the upper bound.
minor comments (1)
- [Definition of Φ(V)] The abstract states that the maximization is concave and thus polynomial-time solvable; a brief remark confirming strict concavity or citing the relevant convex-optimization reference would improve clarity.
Simulated Author's Rebuttal
We thank the referee for the careful reading and for identifying a potential subtlety in the proof of the upper bound in the sandwich inequality. We address this point directly below.
read point-by-point responses
-
Referee: [Abstract, sandwich inequality] Abstract, sandwich inequality: the entropy argument with E[log T] = -γ and Jensen on the concave log yields the lower bound e^{-γ n} widehat P(A) ≤ per(A) via linearity of expectation on ∑ log T_i. However, the same marginals do not imply E[∏ T_i] ≤ 1 for the upper bound per(A) ≤ widehat P(A); when the rows v_i are linearly dependent the joint law of the |v_i^* z|^2 terms can make the expectation exceed 1. The manuscript must therefore supply a distinct Wick-derived inequality or show that the parameterized family achieves the full Donsker–Varadhan supremum. Please cite the specific lemma or subsection establishing the upper bound.
Authors: We agree that the lower bound follows immediately from linearity of expectation and Jensen's inequality on the marginals. The upper bound per(A) ≤widehat P(A) is proved by a separate argument that does not rely on the product of marginals. In Subsection 3.2 we apply the Donsker–Varadhan variational representation directly to the Wick integral formula for per(A). The objective maximized in the definition of Φ(V) is exactly the variational functional that upper-bounds log per(A) for every positive-definite X; the maximum therefore supplies a valid upper bound irrespective of linear dependence among the rows v_i. The log-det and trace terms in the objective encode the joint second-moment structure, so the inequality continues to hold when the rows are dependent. We will add an explicit forward reference to Subsection 3.2 and Lemma 3.3 in the abstract and the statement of the main theorem. revision: yes
Circularity Check
No significant circularity in the sandwich bounds or approximation claim
full rationale
The derivation defines the variational upper bound expression Φ(V) explicitly as a concave maximization and then proves per(A) ≤ e^{Φ(V)} (and the matching lower bound with factor e^{-γ n}) via an entropy argument on the external standard Wick integral representation of the permanent, using only the known independent fact E[log T] = -γ for T ~ Exp(1). The upper bound is not obtained by definition or by renaming the permanent itself; the lower bound follows from Jensen applied to the concave logarithm on the product terms without fitting any parameters to observed permanent values. The cited prior hardness result is external to the present derivation of the approximation algorithm and does not form a self-referential loop. The overall claim is therefore self-contained against standard external mathematical facts rather than reducing to tautology or fitted inputs.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math The Wick integral formula expresses per(A) as an expectation over complex Gaussians or equivalent exponential variables.
- standard math E[log T] = -γ exactly when T ~ Exp(1).
Reference graph
Works this paper leans on
- [1]
-
[2]
Jerrum, Mark and Sinclair, Alistair and Vigoda, Eric , title =. Journal of the ACM , volume =. 2004 , doi =
work page 2004
-
[3]
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices
Anari, Nima and Gurvits, Leonid and Oveis Gharan, Shayan and Saberi, Amin , title =. Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages =. 2017 , doi =. 1704.03486 , archivePrefix =
work page internal anchor Pith review Pith/arXiv arXiv 2017
-
[4]
Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC) , pages =
Gurvits, Leonid , title =. Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC) , pages =. 2003 , publisher =
work page 2003
- [5]
-
[6]
Meiburg, Alexander , title =. Algorithmica , volume =. 2023 , doi =
work page 2023
-
[7]
Ebrahimnejad, Farzam and Nagda, Ansh and Oveis Gharan, Shayan , title =. 2024 , doi =. 2404.10959 , eprinttype =
- [8]
- [9]
- [10]
-
[11]
Geometric Algorithms and Combinatorial Optimization , series =
Gr. Geometric Algorithms and Combinatorial Optimization , series =. 1993 , isbn =
work page 1993
- [12]
- [13]
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.