论文标题
使用高斯字段的永久性估计值
Additive estimates of the permanent using Gaussian fields
论文作者
论文摘要
我们提出了一种随机算法，用于估计$ m \ times m $ rout矩阵$ a $ a $的永久算法。我们通过查看$ a $的永久$ \ mathrm {perm}（a）$ $ a $的期望是对具有特定协方差矩阵$ c $的中心关节高斯随机变量的期望。该算法在对$ n $ times进行采样后，输出此产品的经验平均值$ s_ {n} $。我们的算法在总时间内运行$ O（m^{3} + m^{2} n + mn）$，而失败概率\ begin {equation*} p（| s_ {n} - \ text {perm}（a）|> t）\ leq \ frac {3^{m}}} {t^{2} n} n} \ prod^{2m} _ {i = 1} c_ {ii} c_ {ii}。 \ end {equation*}特别是，我们可以估计$ \ mathrm {perm}（a）$ $ $ε\ bigg（\ sqrt {3^{2m} \ prod^{2m} \ prod^{2m} _ {2m} _ {i = 1}我们将由于Gurvits引起的先前程序进行比较。我们讨论了如何使用半决赛程序找到特定的$ c $，以及与最大切割问题和剪切领域的关系。
We present a randomized algorithm for estimating the permanent of an $M \times M$ real matrix $A$ up to an additive error. We do this by viewing the permanent $\mathrm{perm}(A)$ of $A$ as the expectation of a product of centered joint Gaussian random variables with a particular covariance matrix $C$. The algorithm outputs the empirical mean $S_{N}$ of this product after sampling $N$ times. Our algorithm runs in total time $O(M^{3} + M^{2}N + MN)$ with failure probability \begin{equation*} P(|S_{N}-\text{perm}(A)| > t) \leq \frac{3^{M}}{t^{2}N} \prod^{2M}_{i=1} C_{ii}. \end{equation*} In particular, we can estimate $\mathrm{perm}(A)$ to an additive error of $ε\bigg(\sqrt{3^{2M}\prod^{2M}_{i=1} C_{ii}}\bigg)$ in polynomial time. We compare to a previous procedure due to Gurvits. We discuss how to find a particular $C$ using a semidefinite program and a relation to the Max-Cut problem and cut-norms.
