高次元エクスパンダー: マトロイドの局所エクスパンダー性

今回も高次元エクスパンダーに関する記事となります。前回の記事では単体複体の局所エクスパンダー性を定義し、Oppenheimのトリクルダウン定理を紹介しました。今回の記事ではその応用として以下の前回の記事でも紹介した以下の系を証明したいと思います。

系2.

マトロイド$(V,\mathcal{F})$は局所$0$-エクスパンダーである。

軽く定義を復習しましょう。考えるマトロイドを$X=(V,\mathcal{F})$とし、そのランクを$d$とします。したがって$X(d-2)$は要素数$d-2$の独立集合の全体です。独立集合$\sigma\in X(d-2)$を一つ固定し、そのリンク$X_\sigma$の1-スケルトン$G_\sigma$を考えます。このグラフ$G_\sigma=(V\setminus \sigma,E)$は次で与えられます:

$$\{u,v\}\in V \iff \sigma\cup \{u,v\} \in \mathcal{F}.$$

$G_\sigma$上の単純ランダムウォーク(隣人を一様ランダムに選んで遷移するランダムウォーク)の遷移確率行列を$P_\sigma$とし、$\lambda_2(P_\sigma)$をその2番目に大きい固有値とします。

マトロイドの基の交換を繰り返せば任意の二つの基の間を行き来することができます（詳細は例えばこちらのページの定理1を参照）。同様の議論により、マトロイドはトリクルダウン定理の条件(1-スケルトングラフの連結性)を満たし、トリクルダウン定理の系1より、$\mu_{d-2} = \max_{\sigma\in X(d-2)}\lambda_2(P_\sigma)\leq 0$を示せば冒頭の系2が得られます。

マトロイドに対する$G_\sigma$はどのようなグラフなのでしょうか。実は非常に特徴的な構造を持つことがわかります:

補題1.

任意の$\sigma\in X(d-2)$に対して$G_\sigma$の補グラフの全ての連結成分はクリークである。

証明:

$G_\sigma=(W,E)$とします。$\{u,v\},\{v,w\}\not\in E$ならば$\{u,w\}\not\in E$を背理法を使って示します。まず$\{u,w\}\in E$を仮定します。$G_\sigma$の定義より$S_1:=\sigma\cup \{u,w\}\in \mathcal{F}$です。また、$v$は$G_\sigma$の頂点なので$S_2:=\sigma\cup\{v\}\in\mathcal{F}$も成り立ちます。$S_1,S_2$に対して独立集合族の公理を適用すると$S_2\cup \{u\}\in \mathcal{F}$または$S_2\cup \{w\}\in\mathcal{F}$の少なくとも一方が成り立ちます。しかしこれは$\{u,v\},\{v,w\}\not\in E$に矛盾します。

（証明終）

$G_\sigma$の補グラフの各連結成分を$C_1,\dots,C_\ell\subseteq V$とします。$C_1,\dots,C_\ell$は、補グラフにおける孤立点(次数0の頂点)に対応する連結成分も含みます (例えば$C_1=\{v_1\}$にもなりえるということです)。各$C_i$の指示ベクトルを$v_i$として全ての要素が1の行列を$J$とすると、$G_\sigma$の隣接行列$A$は

\begin{align*} A = J - \sum_{i=1}^\ell v_iv_i^\top\end{align*}

と表せます。したがってCauchyのinterlacing定理より$\lambda_2(A)\leq 0$を得ます。

定理 (Cauchyのinterlacing定理).

対称行列$A\in\mathbb{R}^{n\times n}$の固有値を$\alpha_1\geq \dots \geq \alpha_n$とする。ベクトル$v\in\mathbb{R}^n$に対し、行列$A-vv^{\top}$の固有値を$\beta_1\geq \dots \geq \beta_n$とする。このとき

\[ \alpha_1 \geq \beta_1 \geq \dots \geq \alpha_n \geq \beta_n.\]

特に, $\lambda_2(A-vv^{\top})\leq \lambda_2(A)$.

さて、$G_\sigma$の次数行列$D$と隣接行列$A$を用いて$P_\sigma=D^{-1}A$と表せます。さらに$\lambda_2(A)\leq 0$です。また、$\lambda_2(P_\sigma)=\lambda_2(D^{-1/2}AD^{-1/2})$およびSylvesterの慣性法則により$D^{-1/2}AD^{-1/2}$と$A$の正の固有値の個数は一致するため、$\lambda_2(P_\sigma)\leq 0$を得ます。

定理 (Sylvesterの慣性法則)

対称行列$A\in\mathbb{R}^{n\times n}$と正則行列$S$に対して、$A$と$SAS^\top$の①正の固有値の個数、②負の固有値の個数、③ゼロ固有値の個数は全て一致する。

高次元エクスパンダー: 局所エクスパンダー性の定義とOppenheimのトリクルダウン定理

前回に引き続き高次元エクスパンダーの導入をします。前回の記事では単体複体に関する基本的な用語を定義しました。今回の記事では(純粋な)単体複体に対してエクスパンダー性という性質を定義します。

グラフのエクスパンダー性

元来「エクスパンダー性」という用語はグラフに対して定義される用語です。本記事ではグラフのエクスパンダー性の最低限の定義を述べます。詳しく知りたい方は私が以前mathlogで執筆したこちらの記事をご覧ください。

本記事でグラフと言えば有限集合$V$と2元部分集合族$E\subseteq\binom{V}{2}$の組$(V,E)$で定義されます. 関数$w\colon E\to\mathbb{R}_{\geq 0}$を辺重みと呼び、三つ組$(V,E,w)$を重み付きグラフ (または辺重み付きグラフ) と呼びます。辺の向き、多重辺、自己ループは考えません。

重み付きグラフ$(V,E,w)$に対して重み付き隣接行列$A\in\mathbb{R}_{\geq 0}^{V\times V}$を

\begin{align*} A(u,v) = \begin{cases} 0 & \text{if $\{u,v\}\not\in E$},\\ w(\{u,v\}) & \text{ if $\{u,v\}\in E$} \end{cases} \end{align*}

と定義します。重み付き次数行列$D\in\mathbb{R}_{\geq 0}^{V\times V}$を

\begin{align*} D(u,v) = \begin{cases} 0 & \text{if $u\neq v$},\\ \sum_{w\in V} A(u,w) & \text{ if $u=v$} \end{cases} \end{align*}

とします。最後に遷移確率行列$P$を

\begin{align*} P=D^{-1}A \end{align*}

とします。直感的には頂点$u$からスタートして辺重みに比例した確率で隣接点$v$に移動するランダムウォークを考えたとき、$P(u,v)$の値は頂点$u$から$v$に遷移する確率と等しくなります。なお、$w$を正の定数倍をしても行列$P$は不変です。

$P$は確率行列(各行和が1)なので全ての頂点$u\in V$に対して$\sum_{v\in V}P(u,v)=1$となります。これを行列の形で書くと$P\mathbb{1}=\mathbb{1}$です ($\mathbb{1}\in\mathbb{R}^V$は全ての成分が$1$のベクトル)。すなわち$P$は固有値$1$を持ち、対応する固有ベクトルは$\mathbb{1}$です。この記事の命題1から$P$の他の固有値も全て実数になることが示せます。これらを大きい順に並べて$1=\lambda_1\geq \lambda_2\geq\dots\geq\lambda_{|V|}$とし、これらを第一固有値、第二固有値、などと呼びます。$\lambda_2\leq\lambda$を満たすような重み付きグラフ$G=(V,E,w)$を$\lambda$-エクスパンダーといいます(注)。行列$P$の第二固有値を$\lambda_2(P)$と表します。

注：本来はエクスパンダー性は$\max\{\lambda_2,|\lambda_{|V|}\}\leq\lambda$を満たすグラフとして定義されますことが多いです。ここでは非自明な固有値が絶対値の意味でバウンドされていることを要請しています。しかし単体複体上のランダムウォークの文脈では片側だけのバウンドで事足りるので、ここでは$\lambda_2$の上界のみを考えます。とりあえず$\lambda_2$が小さければ小さいほど良いエクスパンダーであると思ってください。

基本的に考えるグラフは連結であるとします。非連結なグラフの場合、各連結成分の指示ベクトルが固有ベクトルとなり固有値1の多重度が2以上になるからです。

例: 完全グラフ

$G=(V,E,w)$をunit weightの$n$頂点の完全グラフとします。すなわち$|V|=n$で$E=\binom{V}{2}$であり、さらに$w(\{u,v\})=1$とします。全ての成分が$1$の行列を$J$、単に行列を$I$と表すと、$G$の隣接行列は$J-I$と表せます。この行列の第二以降の固有値は全て$-1$なので、遷移確率行列は$\lambda_2=\dots=\lambda_n=-\frac{1}{n-1}$となるので、$G$は$\left(-\frac{1}{n-1}\right)$-エクスパンダーです。

単体複体のエクスパンダー性 (局所エクスパンダー)

重み$w$を持つ純粋な$d$次元単体複体$X=(V,\mathcal{F})$を考えます。次元$k$以下の面全体からなる単体複体$X_k=(V,\mathcal{F}_k)$を$k$-スケルトン ($k$-skelton) といいます。元の単体複体$X$が重み付きならば$k$-スケルトンも同じ重みを考えて重み付きとみなします。

特に$1$-スケルトン$X_1=(V,\mathcal{F}_1)$はグラフ$(V,X(1))$とみなせます。$X$が重み付きならば辺重みを$w_1\colon X(1)\to\mathbb{R}_{\geq 0}$とすることで重み付きグラフ$(V,X(1),w_1)$を考えることができます。これを$X$の$1$-スケルトングラフと呼ぶことにします。

面$\sigma\in\mathcal{F}$のリンク$X_\sigma$に対してその$1$-スケルトングラフを$G_\sigma$とします ($\dim\sigma \leq d-2$とします)。これの遷移確率行列を$P_\sigma$とします。全ての$G_\sigma$が$\lambda$-エクスパンダーであるとき、$X$は局所$\lambda$-エクスパンダーであるといいます。基本的に全ての$G_\sigma$は連結であるとします。

特に、$X$の重み$w_d\colon X(d)\to\mathbb{R}_{\geq 0}$が非ゼロの定数関数ならば、各面$\sigma\in X(d-2)$のリンク$X_\sigma$がなす$1$-スケルトングラフの辺重みは全て同じ値になる (つまり正規化すれば重みなしグラフとみなせる) ことに注意してください。

例: 完全単体複体

各$-1\leq k\leq d$に対して$X(k)=\binom{V}{k+1}$を満たす単体複体を$d$次の完全単体複体と呼びます。これは完全グラフを単体複体に拡張したものになっています。unit weightを考えます (すなわち$w_d(\sigma)=1 (\forall \sigma\in X(d))$で重みづけする)。$\sigma\in X(k)$に対しグラフ$G_\sigma$は$|V|-|\sigma|$頂点の完全グラフとなり、辺重みは一様なので、$\left(-\frac{1}{|V|-|\sigma|-1}\right)$-エクスパンダーです。

Oppenheimのトリクルダウン定理

重み付き単体複体を考えたとき、再帰的に定義された面の重みで定まる行列の固有値を計算することはとても難しく、定義通りにやろうとすると完全単体複体など簡単なものでしかなかなかできないとおもいます。Oppenheimのトリクルダウン(tricling down)定理は次元$k$の面のエクスパンダー性を次元$k+1$の面のエクスパンダー性に帰着する定理です。

$X$を純粋な$d$次元単体複体とします。各$-1\leq k\leq d-2$に対して

\begin{align*} \mu_k = \max_{\sigma\in X(k)} \lambda_2(P_\sigma) \end{align*}

とします。

定理 (Oppenheimのトリクルダウン定理; [1]).

全ての$G_\sigma$が連結であるならば、各$-1\leq k< d-2$に対して\[\mu_k \leq \frac{\mu_{k+1}}{1-\mu_{k+1}}.\]

trickling downとはあえて和訳すると「浸透」という意味です。経済学には「trickle-down」(トリクルダウン)という用語があるらしく、経済活動の活性化が富裕層から下級層に浸透していくみたいな意味があるらしいです。この定理は高次元リンクのエクスパンダー性が低次元リンクに「トリクルダウン」することを主張しています。2018年に証明された定理ですが高次元エクスパンダーの文脈ではOppenheim's Trickling Down Theoremと呼ばれています。知名度の高い和訳はまだないと思いますが、これに倣って私も脳内で「トリクルダウン定理」と呼んでいます。

系1.

$\mu_{d-2}\leq 0$ならば$X$は局所$0$-エクスパンダーである。

すなわち、局所エクスパンダー性を示すには次元$d-2$の面だけ考えれば良いということになります。完全単体複体の例の直前の段落でも述べましたが次元$d-2$の面であれば重み関数も簡単な形になるので局所エクスパンダー性の確認が容易になります。特に、トリクルダウン定理を使うと以下を証明することができます。

系2.

マトロイド$(V,\mathcal{F})$は局所$0$-エクスパンダーである。

端的に言えば系2は「マトロイドはエクスパンダーである」ことを主張しています。グラフエクスパンダーの文脈ではエクスパンダー性はランダムウォークのrapid mixingに直結するのですが似たようなことが単体複体にも成り立ちます。

次回の記事ではトリクルダウン定理を用いて系2の証明を行います。その次の記事でトリクルダウン定理の証明を行います。

文献

[1]. Oppenheim, Izhar. 2018. “Local Spectral Expansion Approach to High Dimensional Expanders Part I: Descent of Spectral Gaps.” Discrete & Computational Geometry 59 (2): 293–330. https://doi.org/10.1007/s00454-017-9948-x.

高次元エクスパンダー: 単体複体とマトロイド

理論計算機科学では近年、高次元エクスパンダーという概念が流行しています。以前の記事でマトロイドの基の一様サンプリングの論文を名前だけ述べました. 理論的な背景としてマトロイドの独立集合族の「エクスパンダー性」が重要になるのですが, この辺りについて最近勉強したので整理していきます.

全体の要約：

• 部分集合で閉じた集合族を単体複体(または独立性システム)という. 特にマトロイドは単体複体の特殊ケースである.
• グラフに対して定義されるエクスパンダー性という性質を単体複体に拡張する.
• マトロイドの独立集合族はそのエクスパンダー性を満たす.
• 飛び道具を使うと基上のランダムウォークのrapid mixingが言えてMCMCが可能になる.

最終目標は証明まで理解することです. 本記事ではその準備として, 単体複体の基本概念を定義していきます.

単体複体

有限集合$V$とその上の部分集合族$\mathcal{F}\subseteq 2^V$の組$X=(V,\mathcal{F})$を考える. $\mathcal{F}$が部分集合で閉じている(すなわち, $\tau\subseteq \sigma$かつ$\sigma\in\mathcal{F}$ならば$\tau\in\mathcal{F}$)とき, $X$を単体複体(simplicial complex)といいます.

単体複体$X=(V,\mathcal{F})$に対し, $\sigma\in\mathcal{F}$を面(face)といい, その次元を$\dim\sigma = |\sigma|-1$で定めます. $\max_{\sigma\in\mathcal{F}}\dim\sigma=d$のとき, $X$は$d$次単体複体といいます. 全ての極大な面の次元が同じとき, $X$は純粋(pure)であるといいます. 各$0\leq k\leq d$に対して$X(k)=\{\sigma\in\mathcal{F}\colon \dim\sigma=k\}$とします. 純粋な$d$次単体複体$X=(V,\mathcal{F})$と各$0\leq k\leq d$に対して$X(k)=\{\sigma\in\mathcal{F}\colon \dim\sigma=k\}$とします. 

幾何的に解釈すると, $0$次の面は点$\{v\}$, $1$次の面は線分$\{u,v\}$, $2$次の面は三角形$\{u,v,w\}$, ...など, 一つ一つの面は単体とみなすことができます.

純粋な$d$次単体複体$X$に対して, 関数$w_d\colon X(d)\to\mathbb{R}_{\geq 0}$を考えます. $0\leq k\leq d-1$に対して$w_k\colon X(k)\to\mathbb{R}_{\geq 0}$を

• $w_k(\sigma) = \sum_{\tau\in X(k+1),\tau\supset \sigma} w_{k+1}(\tau)$

で再帰的に定義し, 重み関数$w\colon \mathcal{F}\to\mathbb{R}_{\geq 0}$を$w(\sigma)=w_{\dim(\sigma)}(\sigma)$で定義します.

面$\sigma\in\mathcal{F}$のリンク$X_\sigma=(V_\sigma,\mathcal{F}_\sigma)$を

\begin{align*} V_\sigma &= \{v\in V\setminus\sigma\colon \sigma\cup \{v\}\in\mathcal{F}\},\\ \mathcal{F}_\sigma &= \{\tau\setminus \sigma\colon \tau\in \mathcal{F},\tau\supseteq \sigma\} \end{align*}

と定義します. リンクもまた単体複体になっており, $X$が純粋な$d$次単体複体ならば$X_\sigma$は純粋な$d-|\sigma|$次単体複体となります.

重み付き単体複体はそのリンク$X_\sigma$に対して以下のように重み$w^\sigma\colon X_\sigma\to\mathbb{R}_{\geq 0}$を誘導します:

\[w^\sigma(\alpha)= \frac{w(\sigma\cup \alpha)}{w(\alpha)}.\]

単体複体に対して以下のような包含関係を表した階層構造(ハッセ図)を想起するのが良いと思います. 

例1. マトロイド

単体複体の重要な例としてマトロイドがあります. 定義などの丁寧な説明はこちらのページにもありますが, 本記事でも簡単に紹介します. マトロイドとは単体複体$(V,\mathcal{F})$であって次の性質を満たすものです:

$|\sigma|<|\tau|$を満たす任意の$\sigma,\tau\in\mathcal{F}$に対してある$v\in\tau\setminus\sigma$が存在して$\sigma\cup\{v\}\in \mathcal{F}$.

この性質よりマトロイドは純粋な単体複体です. 実際, 二つの相異なる極大な面$\sigma,\tau\in\mathcal{F}$が$|\sigma|<|\tau|$を満たすならば上の性質より$\sigma$の極大性に反します. マトロイドを純粋な単体複体とみなしたときの次元に1を加えたものを階数(rank)といいます.

例. グラフ$G=(U,E)$の辺部分集合であって閉路を含まないもの全体からなる辺部分集合族はマトロイドになり, 特にグラフ的マトロイド(graphic matroid)といいます.

例. 体$K$上の行列$A\in K^{n\times m}$の各行を$[n]=\{1,\dots,n\}$で番号付けし, 各行ベクトルを$a_1,\dots,a_n$とします. $[n]$上の部分集合族$\mathcal{F}\subseteq 2^{[n]}$を, 

$F=\{i_1,\dots,i_k\}\in\mathcal{F}\iff$$a_1,\dots,a_{i_k}$が線形独立

で定義したとき, $([n],\mathcal{F})$はマトロイドになり, 特に線形マトロイド(linear matroid)と呼びます.

Remark: 単体複体の文脈では台集合$V$は頂点とみなしますが, (組合せ最適化の文脈における)マトロイドは台集合は辺とみなし$E$で表すことが多いです. 

例2. マトロイド交叉

同じ台集合上の二つのマトロイド$(V,\mathcal{F}_1),(V,\mathcal{F}_2)$に対し,

\[ \mathcal{F}_1\cap \mathcal{F}_2 = \{F\subseteq V\colon F\in \mathcal{F}_1\cap \mathcal{F}_2\}\]

を共通独立集合と呼びます. 組合せ最適化の文脈では共通独立集合のうち要素数最大のものを求める問題はマトロイド交叉問題と呼ばれ, 独立性オラクル(部分集合が$\mathcal{F}_i$に属すかどうかを返すオラクル)があれば多項式時間で解けることが知られています.

共通独立集合の族$\mathcal{F}$に対し, $(V,\mathcal{F})$は単体複体になりますが, 考えるマトロイドによっては必ずしも純粋になるとは限りません.

ロバストPCPとPCP of Proximity

ロバストPCPとPCP of Proximity

PCP定理の証明を構成する二つの重要な要素ロバストPCPとPCP of Proximity (PCPP)について説明します. これらの概念を用いたPCP定理の証明の枠組みはBen-Sassonら[1]によって導入されましたが独立にDinurとReingold[2]のassignment testerと呼ばれる枠組みとほぼ同じです. どれも, 当時知られていた非常に複雑なPCP定理の証明[3]を整理して理解しようとする中で誕生した概念であり, 後にDinur[4]によってエクスパンダーグラフ上のランダムウォークに基づく非常に簡単な証明が与えられました. 彼女はこの業績で2019年にゲーデル賞を受賞しています.

1. 定義の準備

有限長の文字列の集合$L\subseteq \{0,1\}^*$を言語といいます. 計算量理論では, 言語を判定問題(与えられた$x\in\{0,1\}^*$に対して$x\in L$かどうか判定せよという問題)と同一視します. 

同じ長さの二つの文字列$x,y\in\{0,1\}^n$に対してその距離を正規化されたハミング距離で定めます. すなわち$\mathrm{dist}(x,y)=\frac{1}{n}\sum_{i=1}^n \mathbf{1}_{x(i)\neq y(i)}$とします. 文字列の集合$\mathcal{C}\subseteq \{0,1\}^n$と$x\in\{0,1\}^n$に対して$\mathrm{dist}(x,\mathcal{C})=\min_{y\in\mathcal{C}}\mathrm{dist}(x,y)$とします. 特に$\mathcal{C}=\emptyset$のときは$\mathrm{dist}(x,\mathcal{C})=1$と定義します. 関数$D\colon\{0,1\}^n\to\{0,1\}$に対して$D^{-1}(1)=\{x\in\{0,1\}^n\colon D(x)=1\}$とします.

言語$L$に対する検証者とはオラクルアルゴリズム$V^\pi(x)$であってオラクル$\pi$の助けを借りながら$x\in L$かどうかを判定するものを指します. その際, オラクル$\pi\in\{0,1\}^*$は$x\in L$を主張する証明として機能する文字列であり, インデックス$i$に対して$\pi(i)\in\{0,1\}$を返すオラクルとして解釈します. たとえば$L$が充足可能な論理式の全体であるならば, $x$が表す論理式の充足可能性を判断するために例えば$\pi$として$x$の充足割当を持ってくれば証明として機能します. 検証者の能力によって様々なシチュエーションが考えられます.

NP検証者は決定的な多項式時間検証者$V^\pi(x)$であって以下を満たすものです:

1. $x\in L$ならばあるオラクル$\pi$が存在して$V^\pi(x)=1$.
2. $x\not\in L$ならば任意のオラクル$\pi$に対して$V^\pi(x)=0$.

条件1を満たすオラクル$\pi$を本記事ではNP証明と呼ぶことにします. また, NP検証者を持つ言語の集合を$\mathsf{NP}$と表します. 有名な$\mathsf{P}\neq\mathsf{NP}$問題は任意の$L\in \mathsf{NP}$が決定的多項式時間で解けるかどうかを問うています.

PCP検証者は乱択な検証者$V^\pi(x)$であって以下を満たすものです:

1. 任意の$x\in L$に対してあるオラクル$\pi$が存在して$\Pr[V^\pi(x)=1]=1$.
2. ある定数$s>0$が存在して, 任意の$x\not\in L$と任意のオラクル$\pi$に対して$\Pr[V^\pi(x)=0]\geq s$.
3. 任意の$n\in\mathbb{N}$, $x\in\{0,1\}^n$に対して$V^\pi(x)$は高々$q(n)$回のオラクルアクセスを行い, 高々$r(n)$ビットのランダムビットを使う.

条件3の$r(n)$をランダムネス複雑度, $q(n)$を$V$のクエリ複雑度と呼ぶことにします. このような検証者を持つような言語の集合を$\mathsf{PCP}(r,q)$と定義します. 条件1のオラクル$\pi$をPCP証明と呼ぶことにします(*1).

(*1). PCPとはProbabilistic Checkable Proof (確率的検証可能な証明)の略なので, PCP証明という言葉は「証明」の部分が二重になり気持ち悪く本来はPC証明と呼ぶべきですが, そう呼んでしまうとあとでPCPPという用語も出てきてややこしくなるのであえてPCP証明と呼ぶことにします.

PCP定理は$\mathsf{NP}=\mathsf{PCP}(O(\log n),O(1))$を主張する定理です.

2. PCP検証者と制約充足問題

制約充足問題(CSP; Constraint Satisfaction Problem)とは大雑把にいうと「連立方程式の解を見つけよ」という問題です. $n$を変数の個数とし, $[n]=\{1,\dots,n\}$上の集合族$\mathcal{S}$ (つまり各$S\in\mathcal{S}$は$S\subseteq [n]$) とそれで添字づけられた関数族$(D_S)_{S\in\mathcal{S}}$を考えます. ここで各$D_S\colon \Sigma^S\to\{0,1\}$とし, $\Sigma$は有限集合とします (アルファベットと呼びます). 制約充足問題とは

ある$x\in\Sigma^{[n]}$が存在して全ての$S\in\mathcal{S}$に対し$D_S(x|_S)=1$となるか?

を判定する問題です. ここで$x|_S\in\Sigma^S$は$x$の$S$への制限です. 

特に$\Sigma=\{0,1\}$のときのCSPを二値CSP(binary CSP), 全ての$S\in\mathcal{S}$に対して$|S|\leq q$を満たすCSPを$q$-CSPと呼びます. 本記事では特に断りのない限り二値の$q$-CSPを考えます.

PCP検証者$V^\pi(x)$はある集合$S$に対して$\pi|_S$を見て出力を決めるので, インデックス集合$S$(ただし$|S|\leq q$)と関数$D\colon \{0,1\}^n\to \{0,1\}$をランダムに生成し, $D(\pi|_{S})$を出力するアルゴリズムと捉えることができます ($\mathcal{S}$や$D$は入力$x$に依存). これを, $\mathcal{S}$から適当な分布に従ってランダムに選んだ$S$に対して$D_S(\pi|_S)$を出力すると捉えれば, PCP検証者は二値$q$-CSPのインスタンス$(D_S)_{S\in\mathcal{S}}$と同一視することができます. このCSPの変数は$\pi$です. 簡単のため$S$の分布を一様分布とします(*2). このとき, PCP検証者の条件は以下のように書き換えられます:

1. 任意の$x\in L$に対してある$\pi$が存在して全ての$S\in\mathcal{S}$に対して$D_S(\pi|_S)=1$.
2. 任意の$x\not\in L$と任意の$\pi$に対して$\Pr_S[D_S(\pi|_S)=0]\geq s$. すなわち, $D_S(\cdot)$が充足されないような$S$が$s\cdot |\mathcal{S}|$個ある.
3. $|\mathcal{S}|=2^r$かつ$|S|\leq q$である (つまり$\mathcal{S}$上一様ランダムに選ぶときに長さ$r$のランダムビットを使う).

このように捉えるとMAX-SAT(最も多くの節を充足する割当を見つける問題)の近似アルゴリズムの存在性とPCP定理が関係することがわかりやすくなるでしょう.

(*2). $\mathcal{S}$が多重集合であることを許容すれば$S\sim\mathcal{S}$を一様分布とすることができます. 実際, ある集合$S\in\mathcal{S}$が選ばれやすいのであれば, その分だけ$S$を$\mathcal{S}$に追加することで一様分布によってシミュレートすることができます.

3. PCP検証者のロバスト性

条件2の代わりに以下の条件2'を満たすPCP検証者をロバストなPCP検証者といいます:

• (条件2') ある定数$s_1,s_2>0$が存在して任意の$x\not\in L$に対して$\Pr_S[\mathrm{dist}(\pi|_S,D_S^{-1}(1))\geq s_1]\geq s_2$.

条件2'はPCP検証者の条件2よりも強いことを要請しています. 実際, 検証者が条件2'を満たすならば$\Pr[V^{\pi}(x)=0]=\Pr_S[\pi|_S\not\in D^{-1}(1)]\geq \Pr_S[\mathrm{dist}(\pi|_S,D^{-1}(1))\geq s_1]\geq s_2$となるからです.

PCP定理の証明はあるNP完全問題$L$に対してクエリ複雑度の大きいロバストなPCP検証者を構成し, これをPCP of Proximityと組み合わせてクエリ複雑度を下げることによって所望のPCP検証者を得るという流れになります.

4. PCP of Proximity (PCPP)

PCPP検証者とは, 関数$D$(を記述する回路), $D$の割当$x$, 証明$\pi$が与えられたときに$D(x)=1$かどうかを検証する乱択アルゴリズムです. ただし, $x$と$\pi$が両方ともオラクルで与えられ, オラクルへのクエリアクセスの回数が制限されます(*3).

PCPP検証者とは乱択オラクルアルゴリズム$V^{x,\pi}(D)$であって以下を満たすものです:

1. $D(x)=1$ならば, ある$\pi$が存在して$\Pr[V^{x,\pi}(D)=1]=1$.
2. $\mathrm{dist}(x,D^{-1}(1))\geq c_1$ならば$\Pr[V^{x,\pi}(D)=0]\geq c_2$.
3. 任意の$n\in\mathbb{N}$, $x\in\{0,1\}^n,D$に対して$V^{x,\pi}(D)$は高々$q(n)$回のオラクルアクセスを行い, 高々$r(n)$ビットのランダムビットを使う.

直感的にはPCPP検証者とは充足割当からの近さ(proximity)を判定する検証者です. 条件1を満たすオラクル$\pi$をPCPP証明と, $x$を証明と呼ぶことにします. 条件2において$D^{-1}(1)=\emptyset$(つまり$D$が充足不可能)のときは常に$\mathrm{dist}(x,D^{-1}(1))\geq c_1$が成り立つことに注意してください.

(*3). 実際にはペア言語$L\subseteq \{0,1\}^*\times\{0,1\}^*$を考え, $(x,y)\in L$かどうかの検証者として定義されます. この例ではペア言語$L$として$(D,x)\in L\iff D(x)=1$と定義します.

命題. PCPP検証者が存在するならばSATに(同じ$r,q,s$の)PCP検証者が存在する.

証明. SATに対するPCP検証者を構成すればよい. 入力の論理式$C\colon\{0,1\}\to\{0,1\}$に対し, その充足割当$x$を証明としてPCPP検証者$V^{x,\pi}(C)$をシミュレートすれば良い. 実際, $C$が充足可能ならばその充足割当$x$を証明すればよく, 充足可能でないならば$D^{-1}(1)=\emptyset$となり, PCPPの条件2より健全性も成り立つ.

5. ロバストなPCP検証者とPCPP検証者の合成

NP完全な言語$L$に対してロバストなPCP検証者$V_0$であってクエリ複雑度が$Q(n)\gg 1$, ランダムネス複雑度$R$なるものが存在するとします. さらに, クエリ複雑度$q$, ランダムネス複雑度$r$のPCPP検証者の存在性を仮定します (ここでそれぞれの条件2に出てくる定数について$c_1=s_1$を仮定します).

• 2節で説明したように$V_0$をCSPのインスタンス$(D_S)_{S\in\mathcal{S}}$と同一視します. ただし各$|S|=Q$です. $V_0$を走らせたときに得られるランダムな$S\sim\mathcal{S}$に対して関数$D_S$を考えます.
• ペア言語$(D_S,\pi|_S)$に対してPCPP検証者を走らせます. ここで$\pi|_S$は証明として扱います.

こうすると, 全体のクエリ複雑度は$q$, ランダムネス複雑度は$R+r$のPCP検証者を得ることができます. ちゃんとPCP検証者になっているか確認してみましょう.

• $x\in L$ならば全ての$S\in\mathcal{S}$に対して$D_S(\pi|_S)=1$となるため, PCPP検証者も必ず$1$を出力します.
• $x\not\in L$ならば, ロバスト性より確率$s_2$で$\Pr_{S\sim\mathcal{S}}[D_S(\pi|_S)=0]\geq s_1$となります. この事象で条件づけたとき, $c_1=s_1$の仮定より, 確率$c_2$でPCPP検証者は$0$を出力します. すなわち確率$s_2c_2$で上記の検証者は$0$を出力します.

以上の議論より, $R+r=O(\log n)$, $q=O(1)$を満たすように作ればPCP定理が証明できたことになります.

6. まとめ

PCP検証者を構成するために, まず「充足割当からの近さ」を増加させるロバストPCP検証者と「充足割当からの近さ」を検証するPCPP検証者という概念を用いました. 距離に着目するアイデアは誤り訂正符号に基づいたものです.

参考文献

[1] E. Ben‐Sasson, O. Goldreich, P. Harsha, M. Sudan, and S. Vadhan. “Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding.” SIAM Journal on Computing 36 (4): 889–974. https://doi.org/10.1137/S0097539705446810. (2006).

[2] I. Dinur, and O. Reingold. “Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem.” SIAM Journal on Computing 36 (4): 975–1024. https://doi.org/10.1137/S0097539705446962. (2006).

[3] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. “Proof Verification and the Hardness of Approximation Problems.” Journal of the ACM 45 (3): 501–55. https://doi.org/10.1145/278298.278306. (1998).

[4] I. Dinur, “The PCP Theorem by Gap Amplification.” Journal of the ACM 54 (3): 12 – es. https://doi.org/10.1145/1236457.1236459. (2007).

モーメント母関数を使わないChernoff boundの証明

Chernoff boundは, 独立な確率変数$X_1,\dots,X_n$の和$X_1+\dots+X_n$が期待値から外れる確率が$n$に関して指数的に小さくなることを主張する不等式です. Chernoff boundの証明はモーメント母関数$\mathbf{E}[\exp(\lambda X)]$の評価し, それとマルコフの不等式を組み合わせることで与えられます (例えばこのページ参照)

本記事ではImpagliazzoとKabanets(2010)によって与えられた面白い証明を紹介します.

定理.

$X_1,\dots,X_n$を$\{0,1\}$値をとる独立な確率変数で$\mathbf{E}[X_1]=p$とする. 任意の$c>0$に対して

\[\begin{align*} \Pr[X_1+\dots+X_n\geq cn] \leq \mathrm{e}^{-nD(c||p)}.\end{align*}\]

ここで, $D(c||p)=c\log\frac{c}{p} + (1-c)\log\frac{1-c}{1-p}\geq 2(c-p)^2$.

(証明)

パラメータ$q\in[0,1]$に対し, 各$i\in[n]$を独立に確率$q$で含むランダムな部分集合$S$を考え, 確率変数

\[\begin{align*}Z = \prod_{i\in S}X_i \end{align*}\]

とします ($S$と$X$のランダムネスを考える). 定義より

\[\begin{align*}\mathbf{E}[Z]&=\mathbf{E}_S\left[\mathbf{E}_X\left[\prod_{i\in S}X_i\right]\right] \\ &= \mathbf{E}_S\left[p^{|S|}\right] \\ &= (qp+1-q)^n.\end{align*}\]

$\mathcal{E}$を$X_1+\dots+X_n\geq cn$という事象とします. $\mathcal{E}$で条件づけたとき,

\[\begin{align*}\mathbf{E}[Z|\mathcal{E}] &= \mathbf{E}_X\left[\mathbf{E}_S\left[\prod_{i\in S}X_i\middle|\mathcal{E}\right]\middle|\right] \\ &=\mathbf{E}_X\left[\Pr_S[\overline{S}\text{ contains all }i\text{ satisfying }X_i=0|\mathcal{E}]\middle|\mathcal{E}\right] \\ &\geq (1-q)^{(1-c)n}.\end{align*}\]

最後の不等式は, $\mathcal{E}$で条件づけたときに$X_i=0$となる$i$は高々$(1-c)n$個あり, それら全てが$\overline{S}$に含まれる確率で下から抑えることで得ています.

条件付き期待値の性質から$\mathbf{E}[Z]\geq\mathbf{E}[Z|\mathcal{E}]\Pr[\mathcal{E}]$より

\[\begin{align*}\Pr[X_1+\dots+X_n\geq cn]\leq \frac{(pq+1-q)^n}{(1-q)^{(1-c)n}}\end{align*}\]

を得ます. 右辺は$q=\frac{c-p}{c(1-p)}$のとき最小となり, $\mathrm{e}^{-D(c||p)}$となる. (証明終)

参考文献

R. Impagliazzo and V. Kabanets, Constructive Proofs of Concentration Bounds, RANDOM2010.

combinatorial designの構成

集合族$\mathcal{S}$であって任意の相異なる二つの元の共通部分が小さいものを平均計算量理論の文脈でcombinatorial designと呼ぶことがあり, 擬似乱数生成器の構成などにおいて非常に重要な役割を果たします. 具体的には, 台集合$E$上の集合族$\mathcal{S}$であって以下を満たすものを($E$上の)$(d,n)$-designと呼びます.

• 各$S\in\mathcal{S}$に対して$|S|=n$.
• 各$S\neq T\in \mathcal{S}$に対して$|S\cap T|\leq d$.

例1. グリッド

台集合$E=[m]^2$上の集合$S_i=\{(x,y)\in E\colon x=i\text{ or }y=i\}$を考えると $\mathcal{S}=\{S_i\}_{i\in[m]}$は$(2,2m-1)$-designになります.

本記事では$(d,n)$-designの応用先には特に触れず, [NW94]で与えられた以下の$(d,n)$-designを紹介します. Nisan--Wigderson Generatorを知っていても具体的なcombinatorial designを知らない人向けの備忘録です.

定理 (Lemma 2.4 of [NW94]).

各素べき$n$と$d\in\mathbb{N}$に対して, $|E|=n^2$かつ$|\mathcal{S}|=n^{d+1}$を満たす台集合$E$上の$(d,n)$-designが存在する.

証明.

有限体$\mathbb{F}_n$を考え, $E=\mathbb{F}_n^2$とします. $\mathcal{P}_{\leq d}$を$\mathbb{F}_n$上の次数高々$d$の多項式全体の集合とし, 各$p\in\mathcal{P}_{\leq d}$に対して$S_p=\{(x,p(x))\colon x\in \mathbb{F}_n\}$とし, $\mathcal{S}=\{S_p\}_{p\in\mathcal{P}_{\leq d}}$とします. 明らかに$|\mathcal{S}|=|\mathcal{P}_{\leq d}|=n^{d+1}$です.

上で与えた$\mathcal{S}$が確かに$(d,n)$-designになっていることを確認します. まず, 各$S\in\mathcal{S}$は$n$個の点の集合なので確かに$|S|=n$を満たします. 次に$|S_p\cap S_q|>d$を満たす相異なる二つの多項式$p,q\in\mathcal{P}_{\leq d}$が存在すると仮定します. このとき, $p(x)=q(x)$を満たす$x\in\mathbb{F}_n$が$d+1$個以上存在することになりますが, このとき多項式$p-q$は次数高々$d$で$d+1$個の点で$0$になるので, 恒等的に$0$となり, $p\neq q$と矛盾します.

(証明終)

参考文献

[NW94] N. Nisan and A. Wigderson, Hardness vs Randomness, JCCS, 1994.

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

Part1, Part2に引き続き, 有限体$\mathbb{F}_q$上の二つの独立な一様ランダムな行列$A,B\sim\mathbb{F}_q^{n\times n}$が与えられた時に積$AB$を計算せよという問題は最悪計算量 (任意の与えられた$A,B$に対して$AB$を計算する時の計算量) とほぼ一致することを見ました. 具体的にはPart1,2で以下の二つの定理を証明しました.

定理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}'$の乱択を考える.

定理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}'$の乱択を考える.

これら二つの定理はそれぞれ

• 定理1では$\mathcal{A}$の成功確率は$0.75$以上でなければ意味をなさない.
• 定理2では$\mathbb{F}_q$のサイズが大きくなければならない.

という課題を抱えていました. この二つの課題は[Asadi, Golonev, Gur, Shinkar, STOC22]によって次のように解決されました:

定理3([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^{O(\log^4(1/\alpha)}\cdot T(n)$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 0.99$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

定理3の帰着$\mathcal{A}'$の計算時間は$q$に依存しますが, $q$が大きい場合は定理2を使えば良いです.

本記事では定理3の計算時間を少し遅くした以下の定理を証明します.

定理4(weark ver of [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^{O(\alpha^{-2})}\cdot T(n)$時間乱択アルゴリズム$\mathcal{A}'$が存在して全ての$A,B\in\mathbb{F}_q^{n\times n}$に対して$\Pr[\mathcal{A}'(A,B)=AB]\geq 0.99$を満たす. ここで確率は$\mathcal{A}'$の乱択を考える.

定理4の証明のために二つの道具を用意します. 一つは前回の記事で証明した確率的Bogolyubov--Ruzsaの補題です.

補題1 (確率的Bogolyubov--Ruzsaの補題).

集合$D\subseteq \mathbb{F}_q^n$が$|D|\geq \delta |\mathbb{F}_q^n|$を満たすならば, $\dim V\geq n-\delta^{-2}$を満たす線形部分空間$V$であって,

任意の$x\in V$に対して$\Pr_{a,b,c,d\sim \mathbb{F}_q^n}[a,b,c,d\in D|a+b-c-d=x]\geq \delta^5$

を満たすものが存在する.

もう一つの道具はランダム低ランク行列です. パラメータ$k$を受け取り以下のアルゴリズムによって生成された行列を$R_k$とします.

• $v_1,\dots,v_k\sim\mathbb{F}_q^n$を一様ランダムに生成する.
• $v_{k+1},\dots,v_n$をそれぞれ$v_1,\dots,v_k$のランダムな線形結合とする (結合の各係数が$\mathbb{F}_q$上一様ランダム).
• $v_1,\dots,v_n$を並べた行列を$R_k$として出力する.

この時, 以下が成り立ちます (証明は省略).

補題2.

$\dim(V)\geq N-k$を満たす任意の線形部分空間$V$と任意の行列$C\in\mathbb{F}_q^N$に対し, $\Pr[C+R_k\in V]\geq \frac{1}{2q^k}$.

定理4の証明.

$N=n^2$とし, 行列全体の集合$\mathbb{F}_q^{n\times n}=\mathbb{F}_q^N$を線形空間とみなします. $S=\{(A,B)\colon \mathcal{A}(A,B)=AB\}$を$\mathcal{A}$が成功する入力の集合とします. 行列$A\in\mathbb{F}_q^N$を固定し,

$$D_A = \{B\in\mathbb{F}_q^N\colon (A,B)\in S\}$$

とします. $A\sim\mathbb{F}_q^N$が一様ランダムに与えられたときの$|D_A|$の期待値は　$\geq\alpha|\mathbb{F}_q^N|$です.

最後に, $D=\{A\in\mathbb{F}_q^N\colon |D_A|\geq (\alpha/2)|\mathbb{F}_q^N|\}$とします. 直感的には, $A\in D$は$\mathcal{A}$にとって(平均的に)解きやすいインスタンスであるといえます. $A\sim\mathbb{F}_q^N$の時の確率変数$|D_A|/|\mathbb{F}_q^N|$に対して逆マルコフの不等式(Part2, 補題2参照)を適用すると$\Pr_{A\sim\mathbb{F}_q^N}[|D_A|\geq (\alpha/2)|\mathbb{F}_q^N|]\geq \alpha/2$が成り立ちます. すなわち$|D|\geq (\alpha/2)|\mathbb{F}_q^N|$となります.

ここまでで二つの集合$D,D_A$を定義しました. ここからは二段階に分けた帰着を考えます.

1. $A\in D$を満たす任意の入力$(A,B)$に対して$AB$を計算するアルゴリズム$\mathcal{A}_1$を構成する.
2. $\mathcal{A}_1$をサブルーチンとして呼び出すことで$A\not D$に対しても$AB$を計算できるアルゴリズム$\mathcal{A}_2$を構成する.

ケース1: $A\in D$.

この時は$|D_A|\geq \alpha/2$となります. $D_A$に対して補題1を適用すると, $\dim(V)\geq N-4\alpha^{-2}$を満たすある線形部分空間$V$が存在して

$$\forall x\in V,\Pr_{a,b,c\sim \mathbb{F}_q^N,d=a+b-c-x}[a,b,c,d\in D_A]\geq \alpha^5/32$$

です (ここでは$a+b-c-d=x \iff d=a+b-c-x$に注意). $a,b,c,d\in D_A$ならば$\mathcal{A}$は行列積$Aa,Ab,Ac,Ad$を正しく計算できることになるので, $Ad=Aa+Ab-Ac-Ax$に注意すると$Ax$を計算することができます.

さらに, 与えられた$B$に対して補題2より

$$\Pr[B+R_k\in V]\geq \frac{1}{2q^{4\alpha^{-2}}}$$

となります. よって$x=B+R_k$として上の議論を適用することができます.

まとめると$\mathcal{A}_1$は$B\in\mathbb{F}_q^N$を受け取って次のように計算します.

• $R_k$と$S_1,S_2,S_3\sim \mathbb{F}_q^N$をサンプリングし, $S_4=S_1+S_2-S_3-(B+R_k)$とする.
• $AR_k$を計算する ($R_k$のランクが小さくサンプリングした時に線形結合もわかっているので$O(kn^2)$時間で計算できる).
• $C=\mathcal{A}(A,S_1)+\mathcal{A}(A,S_2)-\mathcal{A}(A,S_3)-\mathcal{A}(A,S_4)-AR_k$とする. $AB=C$かどうかをFreivaldのアルゴリズムで確認し, Yesならば出力. そうでなければ最初のステップに戻る.

各繰り返しは$O(T(n))$時間で計算可能です. 最初のステップで$B+R_k\in V$かつ$S_1,S_2,S_3,S_4\in D_A$を満たせば最後のステップで$C=AB$となります. これが起こる確率は上記の解析より$q^{-O(\alpha^{-2})}$です. 従って全体の繰り返し回数を$q^{O(\alpha^{-2})}$でとれば成功確率を$0.99$にでき, この時の$\mathcal{A}_1$の計算時間は$q^{O(\alpha^{-2})}T(n)$です.

ケース2: $A\not\in D$.

ケース2もケース1とほぼ同じです. ここでは$\mathcal{A}_1$をサブルーチンとして使います. $|D|\geq \alpha/2$より, $D$に対して補題1を適用すると, $\dim(V')\geq N-4\alpha^{-2}$を満たすある線形部分空間$V'$が存在して

$$\forall x\in V',\Pr_{a,b,c\sim \mathbb{F}_q^N,d=a+b-c-x}[a,b,c,d\in D]\geq \alpha^5/32$$

です. $a,b,c,d\in D$ならば$\mathcal{A}_1$は任意の$B$に対して行列積$aB,bB,cB,dB$を正しく計算できることになるので, $dB=aB+bB-cB-xB$に注意すると$xB$を計算することができます.

さらに, 与えられた$A$に対して補題2より

$$\Pr[A+R_k\in V']\geq \frac{1}{2q^{4\alpha^{-2}}}$$

となります. よって$x=A+R_k$として上の議論を適用することができます.

まとめると$\mathcal{A}$は$A,B\in\mathbb{F}_q^N$を受け取って次のように計算します.

• $R_k$と$S'_1,S'_2,S'_3\sim \mathbb{F}_q^N$をサンプリングし, $S_4=S_1+S_2-S_3-(A+R_k)$とする.
• $R_kB$を計算する ($R_k$のランクが小さくサンプリングした時に線形結合もわかっているので$O(kn^2)$時間で計算できる).
• $C=\mathcal{A}_1(S_1,B)+\mathcal{A}_1(S_2,B)-\mathcal{A}_1(S_3,B)-\mathcal{A}(S_4,B)-R_kB$とする. $AB=C$かどうかをFreivaldのアルゴリズムで確認し, Yesならば出力. そうでなければ最初のステップに戻る.

ケース1と同じ解析により, アルゴリズム$\mathcal{A}$の計算時間は$q^{O(\alpha^{-2})}\cdot T(n)$になります. (証明終).