Gurvits's exponential BP upper-bound conjecture for the permanent

From papers

Let pp be a non-negative matrix, and let f(n)f(n) be the factor in the BP upper bound

perm(p)Zo-BP(p)f(n).\operatorname{perm}(p)\leq Z_{o\text{-}BP}(p)f(n).

Gurvits's BP upper-bound conjecture. For any non-negative pp, f(n)f(n) is asymptotic to 2n\sqrt{2}^n. This conjecture concerns the worst-case multiplicative gap between the permanent and the BP estimate; the earlier claim that f(n)f(n) is asymptotic to n\sqrt n was disproved by an explicit counterexample. The source gives no resolution of the exponential-factor conjecture.

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.