Source-linked AI summary
Optimal girth-dependent bounds for the Bethe approximation of the permanent
Dingding Dong, Vishesh Jain
TL;DR
Deterministic approximation of the permanent is generally exponentially weaker than randomized approximation, motivating sharper guarantees for the efficiently computable Bethe permanent. The paper confirms Anari’s conjecture by replacing the universal factor with an optimal girth-dependent bound. For support-graph girth at least even g ≥ 4, the comparison is Bethe(A) ≤ per(A) ≤ 2^(2n/g) Bethe(A), with equality examples given by disjoint unions of g-cycles.
Problem
Deterministic polynomial-time guarantees for approximating the permanent remain exponentially weaker than randomized approximation, motivating sharper Bethe-permanent comparisons.
Method
The paper proves a girth-sensitive Bethe-permanent comparison using an information inequality that replaces the universal constant 1/2 by 2/g.
Results
For support-graph girth at least even g ≥ 4, Bethe(A) ≤ per(A) ≤ 2^(2n/g) Bethe(A), and the upper bound is attained by disjoint unions of g-cycles when g divides 2n.
Takeaways & Limitations
The bound is optimal by girth, recovers the universal result at g = 4, and becomes subexponential along graph sequences whose girth tends to infinity.
Takeaways & Limitations
The theorem assumes a nonnegative matrix whose support graph has girth at least an even integer g ≥ 4; degenerate cases with no perfect matching are handled separately.
Abstract
from arXiv · showhide
For an $n\times n$ nonnegative matrix $A$, the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparison \[\operatorname{Bethe}(A) \leq \operatorname{per}(A) \leq 2^{n/2}\operatorname{Bethe}(A).\] The lower bound, due to Gurvits, is attained on forests. The upper bound, due to Anari and Rezaei, is attained by the adjacency matrix of a disjoint union of $4$-cycles. Confirming a conjecture of Anari, we provide an optimal girth-dependent refinement of the above comparison. More precisely, we show that if the bipartite support graph of $A$ has girth at least an even integer $g \geq 4$, then \[\operatorname{Bethe}(A) \leq \operatorname{per}(A) \leq 2^{2n/g}\operatorname{Bethe}(A).\] The upper bound is attained by the adjacency matrix of a disjoint union of $g$-cycles.
1. Introduction
The Bethe permanent offers a deterministic polynomial-time approximation to the permanent, whose deterministic guarantees remain exponentially weaker than randomized approximation. This paper confirms Anari’s conjecture by proving an optimal comparison governed by the support graph’s girth.
- 1. Introduction: #P-hardness makes computing the permanent difficult, unlike determinant computation, while randomized approximation admits a fully polynomial randomized approximation scheme.The deterministic approximation landscape remains exponentially weaker in general.
- 1.2. The Bethe permanent.: The Bethe permanent is computable through convex optimization because its logarithmic variational objective is concave over the fractional perfect matching polytope.This yields polynomial-time approximation to any prescribed multiplicative accuracy.
- 1.2. The Bethe permanent.: Forests achieve exactness, whereas disjoint unions of 4-cycles attain the universal factor 2^(n/2), motivating girth-dependent control of the approximation error.The contrast links approximation quality to the shortest cycle length in the bipartite support graph.
- 1.3. Our contribution.: Disjoint unions of g-cycles attain the upper bound whenever g divides 2n, so the girth-dependent factor is sharp.For a single g-cycle, the permanent is 2 while the Bethe permanent is 1; block-diagonal multiplicativity gives the stated factor.
- 1.3. Our contribution.: 2^(2n/g) is the optimal comparison factor for nonnegative matrices whose bipartite support graph has girth at least even g ≥ 4.The result confirms Anari’s conjecture and recovers the universal bound when g = 4.
- 1.5. Overview of the proof.: The technical proof replaces the universal entropy constant 1/2 by 2/g and uses information inequalities whose averaged correction compensates the girth-estimate deficit.The proof overview identifies this replacement and compensation as central steps.
2. Preliminaries
The preliminaries develop local entropy functionals, generalized information gain, and the Anari–Rezaei functional used to analyze the Bethe permanent. These tools provide concavity, nonnegativity, data processing, and a sharp local estimate.
- Bethe entropy: The Bethe entropy decomposes into local contributions S(q_v) over vertices of a bipartite graph.For each vertex v, q_v is the vector of incident edge marginals in the fractional perfect matching polytope.
- Bethe entropy: S is nonnegative and concave on every probability simplex.
- Information gain: Ψ-information gain measures the expected change in Ψ when observing a finite random variable.For Shannon entropy, it coincides with ordinary mutual information.
- Information gain: For concave Ψ, Ψ-information gain is nonnegative and obeys data processing under a Markov-chain randomization.The proof uses concavity and Jensen’s inequality.
3. Reduction to a good vertex
The proof reduces the girth-dependent permanent bound to an entropy inequality and then to finding a vertex with nonnegative conditional gap. An averaged proposition guarantees such a good vertex, enabling induction after conditioning and deleting matched endpoints.
- Entropy inequality: For bipartite graphs of girth at least even g ≥ 4, Theorem 3.1 gives an entropy inequality for any distribution on perfect matchings.The edge marginals p determine the inequality’s potential and entropy terms.
- Connection to the main theorem: The entropy inequality yields the upper bound in Theorem 1.3 after exponentiation, while the lower bound is Gurvits’s inequality.Sharpness comes from the cycle construction.
- Good vertex: A vertex is good when its conditional gap is nonnegative, and Proposition 3.3 proves that at least one such vertex always exists.The proposition establishes a stronger averaged statement over vertices.
- Inductive reduction: Conditioning on a good vertex’s matched neighbor fixes one edge, after which deleting its endpoints produces an instance of size n − 1 without changing the potential.The induction hypothesis then bounds the conditional entropy and completes the entropy inequality.
- Proof ingredients: The proof of the good-vertex proposition combines a girth-dependent pointwise estimate with an averaged permutation estimate using only that the matching map is a bijection.Matched-neighbor laws and their conditional versions are represented by local marginal vectors.
4. The girth estimate
The proof converts local information quantities into a flow on an auxiliary network, decomposes that flow into components, and projects them to nonbacktracking walks in the support graph. The girth condition bounds these walks and yields the required information inequality.
- Flow construction: The proof converts the information revealed by X⋆ into a flow on an auxiliary network, then uses flow decomposition and the girth assumption.The projected components are nonbacktracking walks in G.
- Flow construction: The locally decomposed coefficients αv_ef produce conserved flow at every auxiliary-network node, so φ is an s–t flow.The flow value is established by Lemma 4.5.
- Flow construction: The auxiliary network alternates traversal arcs along edges of G with transfer arcs that switch to a distinct incident edge.This alternating structure ensures successive projected edges are distinct.
- Girth bound: Every nonempty closed nonbacktracking walk in G has length at least g, because it contains a simple cycle.This is the point where the graph's girth assumption enters the component bounds.
- Girth bound: The component bounds are reassembled by weighting each path and cycle component by its flow-decomposition coefficient and summing.The resulting identities are then translated into the change produced by conditioning on X⋆.
5. The permutation estimate
The permutation estimate develops a concave functional Γ through a deletion recursion and applies it to random permutations. A Γ-information inequality then controls the information gained about each matched neighbor.
- Deletion and concavity: The deletion identity remains well defined for point-mass distributions by interpreting the relevant terms as zero.Conditioning on J produces point masses, where Γ vanishes.
- Deletion and concavity: The paper proves that the functional Γ : ∆d → R is concave for every d ≥1.The proof uses induction, perspectives of Γd−1, and concavity of S.
- Permutation inequality: For any random permutation and fixed coordinate Xj, the sum of Γ-information gained about Xj from observing the other coordinates is at least its local Bethe entropy.This is the content of Lemma 5.3.
- Permutation inequality: The proof applies data processing to the Markov chain Xj–T–W after representing W as a uniformly selected remaining permutation value.Concavity of Γ supplies the needed information inequality.
- Permutation inequality: Applying the permutation lemma to X and X−1, then summing over both vertex classes, yields Proposition 3.5.Forward and inverse-coordinate information sums agree even though individual terms need not.