Gurvits's doubly stochastic permanent inequality conjecture

From papers

Let ϕ\phi be a doubly stochastic n×nn\times n matrix, so that its entries are non-negative and every row and column sums to 11. The permanent is denoted by perm(ϕ)\operatorname{perm}(\phi). Gurvits's permanent inequality conjecture. The following inequality holds:

perm(ϕ)2n(i,j)(1ϕij)1ϕij.\operatorname{perm}(\phi)\leq \sqrt{2}^n\prod_{(i,j)}(1-\phi_{ij})^{1-\phi_{ij}}.

If true, this inequality would imply a deterministic polynomial-time algorithm approximating the permanent of an n×nn\times n non-negative matrix within relative factor 2n\sqrt{2}^n. The source does not state that the inequality has been proved or disproved.

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).

Additional references

2 papers in this index state this conjecture (2011). The statement above is taken from the most recent of them; the others are arXiv:1107.4196.

Solutions 0

No solutions have been posted yet.