{"id":"arxiv/2608.31061","url":"https://arxiv.org/abs/2608.31061","tags":["cs.DS","math.CO"],"score":0,"title":"Structural Corrections to the Bethe Approximation of the Permanent","domain":"cs.DS","source":"arxiv","authors":["Ijay Narang","Will Perkins"],"reviews":0,"subject":"cs.DS","summary":"We study deterministic approximation algorithms for the permanent of a nonnegative matrix through the Bethe permanent, an approximation computable in polynomial time. The tight analysis of Anari and Rezaei gives a universal comparison between the permanent and the Bethe permanent within a factor $(\\sqrt 2)^n$. The simple example of the unweighted $4$-cycle $C_4$ (or a union of disjoint $C_4$'s) shows that this bound is tight. We show that such $4$-cycle obstructions can be identified and exploited algorithmically. Given a Bethe optimizer, our algorithm identifies nearly isolated weighted…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-31","reactions":{}}