A new algorithm in theoretical computer science gives a deterministic polynomial-time approximation for the permanent, the matrix quantity at the center of the work, with an exponential base strictly below the square root of two. That improves on the canonical Bethe guarantee. The result applies to the stated class of nonnegative rational square matrices. Its guarantee is one-sided: the constructed paired certificate does not exceed the exact permanent.
This is a proof-and-algorithm result, not an empirical study. It is quantified over mathematical matrix instances rather than participants or an observational dataset. The paper's central question is whether the canonical Bethe certificate can be augmented with certificates built from selected pairs of rows. In this setting, a certificate is a computable quantity used to bound the exact permanent from one side.
Finding structure in the gap
The proof tracks the slack in the upper Bethe bound, meaning the amount of room between that bound and the exact permanent. It gives an exact decomposition into three nonnegative parts: Bethe suboptimality, the sum of row deficits, and an averaged sequential Kullback-Leibler divergence between the true and sequential permutation distributions. The identity lets the analysis separate the different sources of slack when the bound is close to the target.
A row-stability lemma supplies the next link. It says that a probability row's total coordinate-by-coordinate distance from the set of half-half vectors is bounded by a universal constant times the fourth root of its row deficit. In plain terms, a row with a small deficit must be close to splitting its weight evenly across two entries. The proof uses that pattern to identify rows that can be paired.
The graph analysis then completes these patterns into a two-regular graph and looks for clean pairs of good rows. A clean pair forms a two-by-two component, described in the paper as K2,2. The stated lower bound on the number of vertex-disjoint pairs is , where n is the matrix order, b is the number of bad rows, and N is the number of good rows in components containing at least three rows. Bad rows and longer components therefore reduce the number of candidates available to the certificate.
Why a pair can do more than two singles
Those candidates feed a paired lower certificate that is valid for every row matching, so the pairs can be selected algorithmically. The comparison is with treating the same two rows as separate singleton rows, and the sought-after condition is a gain ratio greater than one. For a clean two-by-two component with sufficiently small four-edge transfer cost and sufficiently small regularization, the proof obtains a strictly positive constant logarithmic gain. That local gain is the ingredient used in the construction that reaches a universal approximation base below the square root of two.
To make the needed point computable, the method maximizes an entropy-regularized Bethe objective. The regularized problem has a unique interior maximizer, remains within a controlled loss of the unregularized Bethe optimum, and exposes positive row and column scaling factors through its optimality equations. An exact transfer identity links the regularized suboptimality and row entropy terms to the total transfer cost over matrix entries. Together, these steps connect the global slack analysis to the local four-edge gain.
A theorem, not a benchmark
Zero entries are handled through one-sided smoothing, with finite precision treated as a separate implementation issue. The authors state that the computation keeps rational intermediates, requested precisions and the final output at polynomial bit length. Arithmetic, optimization, elementary-function evaluation and maximum-weight matching are all stated to run in polynomial time. This is why the result is presented as a deterministic polynomial-time algorithm rather than only a mathematical existence claim.
The result has clear boundaries. The supplied analysis reports no empirical benchmarks, instance-level error distributions or observed runtime measurements, and it does not establish that the base is optimal. The approximation constant is not optimized, so the theorem gives a strict mathematical guarantee without settling the best possible universal base or the algorithm's performance across particular matrix families.
The work is an arXiv preprint, version v1 dated 28 Aug 2026. It discloses that the proof was developed in interaction with ChatGPT 5.6 Sol Pro and that Codex assisted with proof checking and manuscript work; the author subsequently verified the results. Funding is not reported in the supplied text.
The open questions are practical and mathematical: how small the universal base can ultimately be, how the executable algorithm behaves across different matrix families, and whether similar certificate additions can improve other Bethe-style counting approximations.
Paper data and sources
Original title: Beyond the Bethe Approximation of the Permanent
Authors: Nima Anari
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-28
DOI: Not available
Original paper · Full text