ランダム行列の行列積 part 1

 二つの行列$A,B\in\mathbb{F}_q^{n\times n}$が与えられたときにその積$AB$を計算せよという問題はこれまで多くのアルゴリズムが提案されており, 2022年4月現在では[Alman, Williams, SODA2021]による$O(n^{2.37286})$時間が(漸近的な意味で)最速のアルゴリズムとされています. 行列積は$n^2$個の値を計算する問題なので明らかに$\Omega(n^2)$時間かかるので, $2$と$2.37286$の間に限界があるというわけです.

本記事では「$A,B$が$\mathbb{F}_q^{n\times n}$上一様ランダムに与えられた時に$AB$を計算せよ」というランダム行列に対する行列積を計算する問題を考えます.

幾つかの問題ではランダムなインスタンスに対して比較的効率的に問題が解けるということが知られています. 例えばランダムグラフの文脈ではErdős–Rényiグラフ$G(n,p)$上では$O(n^{4+o(1)})$時間でハミルトン閉路を検出し見つけることができます [Bollobás, Fenner, Frieze, Combinatorica, 1987].

果たして行列積は簡単になるでしょうか？

実は答えは(ある意味で)否です. というのも, ランダムな行列の行列積を高速に計算するアルゴリズムがあればそれとほぼ同等の時間で全ての行列に対して行列を計算する乱択アルゴリズムが存在します.

本記事では以下を証明していきます.

定理1 [Blum, Luby, Rubinfeld, 1993]

ある$T(n)$時間アルゴリズム$\mathcal{A}$が存在して$\Pr_{A,B\sim\mathbb{F}_q^{n\times n}}[\mathcal{A}(A,B)=AB]\geq 1-\epsilon$を満たすならば, ある$O(T(n))$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 1-4\epsilon$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

証明.

以下で与えられるアルゴリズム$\mathcal{A}'$を考えます. 入力を$A,B$とします.

1. 一様ランダムな行列$R_1,S_1\sim \mathbb{F}_q^{n\times n}$をサンプリングし, $R_2=A-R_1,S_2=B-S_1$とする.
2. $\sum_{i,j\in\{1,2\}}\mathcal{A}(R_i,S_j)$を出力する.

このアルゴリズムは4回$\mathcal{A}$を呼び出しているので計算時間は$O(T(n))$です. さらに, $\Pr_{R_1,S_1}[\mathcal{A}'(A,B)=AB]\geq 1-4\epsilon$を満たします.

実際, $R_2,S_2$の(周辺)分布はそれぞれ$\mathbb{F}_q^{n\times n}$上一様なので, 各$i,j\in\{1,2\}$に対して$\Pr[\mathcal{A}(R_i,S_j)=R_iS_j]\geq 1-\epsilon$です. よってunion boundより$\Pr[\forall i,j\in\{1,2\},\mathcal{A}(R_i,S_j)=R_iS_j]\geq 1-4\epsilon$を得るので, この確率で出力値は

$$\sum_{i,j\in\{1,2\}}R_iS_j=(R_1+R_2)(S_1+S_2)=AB$$

を得ます. (証明終)

BLR93の定理において$\epsilon=1/4-\delta$であれば$\mathcal{A}'$の正答確率が$4\delta$になるので, $100\delta^{-1}$回繰り返せば高確率でそれらの出力の中に一つ以上の正解が含まれています. ところが行列積は乱択を使えば簡単に検証 ($A,B,C$に対して$AB=C$かどうかは$O(n^2)$時間で判定. Freivald's algorithmと呼ばれる.) できるので, 出力された$100\epsilon^{-1}$個の行列の中にある正解がどれかは分かります.

しかしながら証明の解析でunion boundをとっている都合上どうしても$\epsilon\geq 1/4$にはできません.

次回以降のpartではこの$\epsilon\geq 1/4$のケースに対しても上記の定理のような「最悪時から平均時への帰着」が存在することを示した[Asadi, Golovnev, Gur, Shinkar, STOC2022]を紹介したいと思います.