Structural Corrections to the Bethe Approximation of the Permanent

@misc{narang2026structural,
  title = {{Structural Corrections to the Bethe Approximation of the Permanent}},
  author = {Ijay Narang and Will Perkins},
  howpublished = {arXiv},
  year = {2026},
  month = aug,
  doi = {10.48550/arxiv.2608.31061},
  eprint = {2608.31061},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.31061},
}

TY  - UNPB
TI  - Structural Corrections to the Bethe Approximation of the Permanent
AU  - Ijay Narang
AU  - Will Perkins
PY  - 2026
DA  - 2026/08/31
PB  - arXiv
DO  - 10.48550/arxiv.2608.31061
UR  - https://arxiv.org/abs/2608.31061
AB  - 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 (√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 2×2 blocks and peels off a vertex-disjoint family of them. If the total weighted correction is large, we can improve the Bethe approximation; if it is small, we show that the Bethe permanent is within a factor of (√2 − ε)^n of the truth. Combining these facts, we obtain a deterministic polynomial time (√2−ε)^n-approximation algorithm for the permanent of an arbitrary nonnegative n× n matrix, where ε>0 is some absolute constant.
ER  -