本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2012
摘要
Since the celebrated work of Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671-697], we have known that the permanent of a matrix with entries in {0, 1} can be approximated in randomized polynomial time by using a rapidly mixing 馬可夫 chain to sample perfect matchings of a bipartite graph. A separate strand of the literature has pursued the possibility of an alternate, algebraic polynomial-time approximation scheme. These schemes work by replacing each 1 with a random element of an algebra A and considering the determinant of the resulting matrix. In the case where A is noncommutative, this determinant can be defined in several ways. We show that for some estimators based on the conventional determinant, the critical ratio of the second moment to the square of the first-and therefore
※ 此為已發表論文，全文需透過期刊付費取得