Gurvits's exponential BP upper-bound conjecture for the permanent
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.
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
Sign in to submit a solution.
No solutions have been posted yet.