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

前回の記事に引き続き, 独立一様ランダムな二つの行列$A,B\sim\mathbb{F}_q^{n\times n}$が与えられた時に積$AB$を計算せよという問題を考えます.

前回は[Blum, Luby, Rubinfeld, 1993]による以下の定理を証明しました. ここで有限集合$S$に対して$x\sim S$と書いた時は$x$は$S$上一様ランダムに選ばれた元と解釈してください.

定理1(BLR93).

ある$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}$の成功確率が$0.75$より小さい (即ち$\epsilon\geq 1/4$) と$\mathcal{A}'$の成功確率が$0$になってしまうため, $\mathcal{A}$は75%より多くのインスタンスに対して正解しなければなりませんでした. 本記事では$\mathbb{F}_q$が大きいという仮定の下でこの課題を乗り越え, 「$\mathcal{A}$の成功確率が1%でも$\mathcal{A}'$は高確率で成功する」ような$\mathcal{A}'$を構成していきます.

定理2(folklore; explicitly in [Asadi, Golonev, Gur, Shinkar, STOC22]).

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

定理2の証明は[Asadi, Golonev, Gur, Shinkar, STOC22]によって明示的に与えられていますが, その証明はパーマネントのランダム自己帰着の文脈などでよく知られる手法に基づいています (なおAGGSの本質的な貢献は$\mathbb{F}_q$が小さい場合に帰着を与えたという点にあります). AGGSが与えた帰着では$\mathcal{A}'$の計算時間は$O(T(n)/\alpha^4)$になっていますがここで紹介する帰着はそれより少しだけ高速で$O(T(n)/\alpha^2)$になっています.

1. 準備

定理2の証明のために幾つかの準備をします.

補題1 (Freivald's algorithm).

$A,B,C\in\mathbb{F}_q^{n\times n}$が与えられたとき, $AB=C$かどうかを判定する問題を考える. この問題を成功確率$1-\epsilon$で解く$O(n^2\log(1/\epsilon))$時間アルゴリズムが存在する.

証明.

$v\sim\mathbb{F}_q^n$を一様ランダムなベクトルとして, $ABv=Cv$かどうかをチェックします. 行列とベクトルの積なのでこれは$O(n^2)$時間でチェックできます. もし$ABv\neq Cv$ならば明らかに$AB\neq C$なのでNOと出力し, そうでなければ改めて$v\sim\mathbb{F}_q^{n\times n}$をサンプルしなおして同じことを繰り返し, 一度もNOにならなかったらYESを出力します.

このアルゴリズムは$AB=C$ならば必ずYESを出力する一方で, $AB\neq C$ならば

$$\Pr[ABv= Cv]=\Pr[(AB-C)v= 0]=\Pr[v\in \mathrm{ker}(AB-C)] \leq 1/q$$

なので各試行では確率$1-1/q\geq 1/2$でNOを出力します. 最後の不等式は$AB-C\neq 0$より$\mathrm{ker}(AB-C)$の次元は$n-1$以下であり, $|\mathrm{ker}(AB-C)|\leq |\mathbb{F}_q^n|/q$であることを使いました. (証明終).

補題2 (逆マルコフの不等式).

$X$を$[0,1]$上に値をとる確率変数とし, $\mu=\mathrm{E}[X]\in(0,1)$とすると,

$\Pr[X\geq \mu/2] \geq \mu/2.$

証明.

非負の確率変数$1-X$にマルコフの不等式を適用すると, 任意の$c\in(0,1)$に対して

$$\Pr[X\leq c] = \Pr[1-X\geq 1-c] \leq \frac{1-\mu}{1-c} = 1-\frac{\mu-c}{1-c} \leq 1-(\mu-c).$$

これに$c=\mu/2$を代入すればよい. (証明終)

系3.

$X_1,\dots,X_m$を$\{0,1\}$上に値をとる(独立とは限らない)確率変数で全ての$i\in[m]$に対し$\mathbb{E}[X_i]=\alpha$を満たすとし, $X=\sum_{i=1}^m X_i$とすると, $\Pr[X\geq m\mu/2]\geq \mu/2$.

2. 定理2の証明

与えられた行列を$A,B$とします. $R,S\sim\mathbb{F}_q^{n\times n}$を二つの独立な一様ランダムな行列とし, $f,g\colon\mathbb{F}_q\to\mathbb{F}_q^{n\times n}$を $f(t)=A+tR, g(t)=B+tS$とします. $f(t)$と$g(t)$は各成分が$\mathbb{F}_q[t]$に属する一次多項式行列とみなすことができます. このとき積$f(t)g(t)$の各成分は二次多項式になっているので, 相異なる三つの点$1\leq t_1<t_2<t_3\leq q-1$に対して$f(t_i)g(t_i)$ ($i=1,2,3$)が計算できれば多項式補間によって$f(t)g(t)$の各成分を得ることができます. そうすれば定数項$f(0)g(0)=AB$が計算できます.

各$t=1,\dots,m$ ($m\leq q-1$は後で決めるパラメータ) に対して確率変数$X_t$を, $\mathcal{A}(f(t),g(t))=f(t)g(t)$ならば$X_t=1$, そうでなければ$X_t=0$とします. 固定した$t\neq 0$に対して$f(t)$と$g(t)$はそれぞれ$\mathbb{F}_q^{n\times n}$上一様ランダムな行列なので, $\mathbf{E}[X_t]=\Pr_{R,S}[\mathcal{A}(f(t),g(t))=f(t)g(t)]=\alpha$です. よって系3より

$$\Pr[X\geq m\alpha/2]\geq \alpha/2$$

を得ます. ここで$m=\lceil6/\alpha\rceil$とすれば (ここで$q-1\geq 6/\alpha$の仮定を利用する), 確率$\alpha/2$で$X\geq 3$となり前の段落で述べた$1\leq t_1<t_2<t_3\leq m$が存在します. しかも補題1より$f(t)g(t)=\mathcal{A}(f(t),g(t))$かどうかは効率的に検証できるので$t_1,t_2,t_3$を求めることができます. 最後に求めた$t_1,t_2,t_3$及び$f(t_1)g(t_1),f(t_2)g(t_2),f(t_3)g(t_3)$を使って多項式補間すれば$f(0)g(0)$を計算できます.

まとめると次のアルゴリズムを得ました:

1. $R,S\sim\mathbb{F}_q^{n\times n}$を一様ランダムな行列とする.
2. $f(t)=A+tR,g(t)=B+tS$とし, $m=\lceil 6/\alpha \rceil$とする.
3. 各$t=1,\dots,m$に対して$C_t=\mathcal{A}(f(t),g(t))$を計算し, 補題1のアルゴリズムを使って$f(t)g(t)=C_t$かどうかをチェックし, $f(t)g(t)=C_t$となるような最初の三つの$t$を$t_1,t_2,t_3$とする. そのような$t_i$が三つとれなければステップ1に戻る.
4. $f(t_1)g(t_1), f(t_2)g(t_2), f(t_3)g(t_3)$を使って$f(t)g(t)$の各成分を多項式補間し, $f(0)g(0)$を出力する.

ステップ4に進む確率は$\alpha/2$なので, ステップ1から3を$O(\alpha^{-1})$回繰り返せば高確率で一度はステップ4に進むため, アルゴリズムは成功します. 各繰り返しではステップ3で$m$回$\mathcal{A}$を呼び出しているので, $\mathcal{A}'$の全体の計算時間は$O(T(n)/\alpha^2)$となります. (証明終).

次回のpartでは体$\mathbb{F}_q$が小さい場合に[Asadi, Golonev, Gur, Shinkar, STOC22]によって与えられた帰着を紹介します.