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

At least 14 years old · documented by

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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.