The fractional BP upper-bound conjecture for the permanent at gamma equals minus one-half

From papers

Let pp be a non-negative matrix, and let Zo-f(γ)(p)Z_{o\text{-}f}^{(\gamma)}(p) denote the fractional BP partition-function estimate at parameter γ\gamma. In particular, write Zo-fγ=1/2(p)Z_{o\text{-}f}^{\gamma=-1/2}(p) for its value at γ=1/2\gamma=-1/2. Fractional BP upper-bound conjecture. For any non-negative pp,

perm(p)Zo-fγ=1/2(p).\operatorname{perm}(p)\leq Z_{o\text{-}f}^{\gamma=-1/2}(p).

This is presented as a reformulation of the preceding exponential BP-bound conjecture, motivated by the doubly degenerate block example where the bound is attained. The source gives no resolution of this inequality.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

M. Chertkov and A. B. Yedidia, “Approximating the Permanent with Fractional Belief Propagation”, arXiv:1108.0065 (2013).

Solutions 0

No solutions have been posted yet.