Barvinok's concentration conjecture for the Frobenius permanent estimator

At least 16 years old · documented by

Let AA) be an n×nn\times n matrix with entries in {0,1}\{0,1\}. For a matrix AA, define M(A)M(A) by

M(A)ij=ρijAij,M(A)_{ij}=\rho_{ij}A_{ij},

where the ρij\rho_{ij} are chosen independently from the Gaussian distribution on Ad\mathcal{A}_d. Define M(\mathds1)M(\mathds 1) similarly by M(\mathds1)ij=ρijδijM(\mathds 1)_{ij}=\rho_{ij}\delta_{ij}. Let perm⁡A\operatorname{perm} A denote the permanent of AA, and let ∥⋅∥\|\cdot\| denote the Frobenius norm. Barvinok's concentration conjecture. There is a sequence of constants γd\gamma_d with

lim⁡d→∞γd=1,\lim_{d\to\infty}\gamma_d=1,

such that, for every ϵ>0\epsilon>0,

lim⁡n→∞Pr⁡[(γd+ϵ)−nperm⁡A≤∥M(A)∥2∥M(\mathds1)∥2≤(γd+ϵ)nperm⁡A]=1.\lim_{n\to\infty}\Pr\left[(\gamma_d+\epsilon)^{-n}\operatorname{perm} A\leq\frac{\|M(A)\|^2}{\|M(\mathds 1)\|^2}\leq(\gamma_d+\epsilon)^n\operatorname{perm} A\right]=1.

This conjecture asserts asymptotic concentration of the Frobenius estimator around the permanent, up to a factor that becomes mild as dd grows. The paper states that its results do not address the conjecture directly, so its resolution is not established here.

References

Primary source

Cristopher Moore and Alexander Russell, “Approximating the Permanent via Nonabelian Determinants”, arXiv:0906.1702 (2009).

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.