Barvinok's concentration conjecture for the Frobenius permanent estimator
Let ) be an matrix with entries in . For a matrix , define by
where the are chosen independently from the Gaussian distribution on . Define similarly by . Let denote the permanent of , and let denote the Frobenius norm. Barvinok's concentration conjecture. There is a sequence of constants with
such that, for every ,
This conjecture asserts asymptotic concentration of the Frobenius estimator around the permanent, up to a factor that becomes mild as 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
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.