Beyond the Bethe Approximation of the Permanent

@misc{anari2026beyond,
  title = {{Beyond the Bethe Approximation of the Permanent}},
  author = {Nima Anari},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2608.28031},
  eprint = {2608.28031},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.28031},
}

TY  - UNPB
TI  - Beyond the Bethe Approximation of the Permanent
AU  - Nima Anari
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2608.28031
UR  - https://arxiv.org/abs/2608.28031
AB  - The canonical Bethe approximation gives a deterministic approximation to the permanent of every nonnegative matrix within a factor of (√2)^n. We improve the base of this exponential factor: for some absolute constant c<√2, there is a deterministic polynomial-time c^n-approximation for the permanent of every nonnegative matrix. This shows that the canonical Bethe guarantee is not a barrier for deterministic approximation of the permanent. The proof augments the Bethe lower bound with a new certificate tailored to matrices on which that lower bound loses nearly the full factor. The author supplied the high-level plan of attack, and the proof was developed in an interaction with ChatGPT 5.6 Sol Pro. The author subsequently verified the results. Codex assisted with proof checking, manuscript assembly, and typesetting.
ER  -