Gurvits's exponential BP upper-bound conjecture for the permanent
Let be a non-negative matrix, and let be the factor in the BP upper bound
Gurvits's BP upper-bound conjecture. For any non-negative , is asymptotic to . This conjecture concerns the worst-case multiplicative gap between the permanent and the BP estimate; the earlier claim that is asymptotic to was disproved by an explicit counterexample. The source gives no resolution of the exponential-factor conjecture.
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.