Optimal girth-dependent bounds for the Bethe approximation of the permanent

What the math gives to ML

The paper gives a sharp, structural error guarantee for replacing the permanent of a nonnegative matrix by its polynomial-time Bethe approximation: the multiplicative gap improves from $2^{n/2}$ to $2^{2n/g}$ when the bipartite support graph has girth at least $g$. This suggests a matching-aware neural normalization or routing layer whose partition function is approximated by Bethe inference, with a known worst-case log-error controlled by the sparsity pattern rather than only its size. The most promising transfer is to design fixed high-girth sparse assignment graphs for MoE routing, set matching, or permutation-equivariant attention, and use the Bethe free-energy optimizer as a differentiable surrogate for the intractable permanent.