Gurvits's doubly stochastic permanent inequality conjecture

At least 14 years old · documented by

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.

References

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.

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.