本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
自從 Jerrum、Sinclair 和 Vigoda 的著名工作以來 [J. ACM, 51 (2004), pp. 671-697]，我們知道，通過使用快速混合馬可夫鏈對二分圖的完美匹配進行採樣，可以在隨機多項式時間內近似具有 {0, 1} 中的條目的矩陣的值。另一部分文獻探討了替代代數多項式時間近似方案的可能性。這些方案的工作原理是將每個 1 替換為代數 A 的隨機元素，並考慮所得矩陣的行列式。在 A 不可交換的情況下，可以透過多種方式定義該行列式。我們證明，對於一些基於傳統行列式的估計量，當 A 是 d x d 矩陣的代數時，二階矩與一階矩平方的臨界比（因此我們需要獲得永久的良好估計所需的試驗次數）為 (1 + O(1/d))(n)。這些結果一般可以擴展到群代數和半簡單代數。我們也研究了 Barvinok 的對稱行列式，顯示當 d 夠大時，所得估計量的變異數很小。然而，如果 d 是常數（這是已知有效演算法的唯一情況），我們表明臨界比率超過 2(n)/n(O(d))。因此，我們的結果並沒有為永久提供新的多項式時間近似方案。事實上，他們認為用代數方法來逼近恆值面臨重大障礙。我們使用圖表技術來獲得這些結果，其中我們將矩陣乘積表示為張量乘積的收縮。當根據高斯分佈隨機選擇這些矩陣時，我們可以根據適當隨機排列的循環結構來評估這些乘積的跡。在對稱情況下，我們的估計是透過與對稱群的特徵理論的連結得出的。