Barvinok's concentration conjecture for the Frobenius permanent estimator

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 permA\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

limdγd=1,\lim_{d\to\infty}\gamma_d=1,

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

limnPr[(γd+ϵ)npermAM(A)2M(\mathds1)2(γd+ϵ)npermA]=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.

Sources & referencesView supporting material

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.