VibeMathedMath problems solved by AI

The Optimal Approximation Ratio for Permanents of PSD Matrices

What is the best deterministic polynomial-time approximation ratio for the permanent of a Hermitian positive semidefinite matrix? Resolved up to lower-order terms in the exponent: an explicit concave maximisation P^(A)\widehat P(A) satisfies e−γnP^(A)≤per(A)≤P^(A)e^{-\gamma n}\widehat P(A) \le \mathrm{per}(A) \le \widehat P(A), giving a deterministic e(γ+ε)ne^{(\gamma+\varepsilon)n}-approximation for every ε>0\varepsilon > 0 and matching the known e(γ−ε)ne^{(\gamma-\varepsilon)n} hardness, where γ\gamma is the Euler-Mascheroni constant.

Result
Proved
Status
Resolved
AI contribution
AI co-developed
Method
Argument
Field
Approximation algorithms
Posed by
open in the approximation algorithms literature
Year posed
—
Years open
—
Solved
2026-05-21
Model
GPT 5.5 Pro Extended
Vendor
OpenAI
Collaborators
Nima Anari, Farzam Ebrahimnejad
Verification
Unreviewed
Publication
Preprint
Significance
30 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What the AI did

The authors describe two different interaction styles converging on the same result: the first author's interaction was one-shot, the second author's involved high-level guidance. Both state they verified the theorem and proof themselves. Codex was used separately to assemble and typeset the manuscript, and the disclosure keeps that clerical use distinct from the mathematics.

Verification

Both authors state they verified the theorem and proof. The result is a sandwich inequality around an explicit concave maximisation, so it is checkable by following the argument. arXiv preprint, not peer-reviewed.

Source

arXiv:2605.21946 - Optimal Approximation of the Permanent of Positive Semidefinite Matrices

Discussion