Barvinok's concentration conjecture for the Frobenius permanent estimator
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.