エントロピーを使ったXOR補題の証明

嬉しいことに今年STOCに2本の論文を通せたのですが、そのうち一本は、XOR補題（の自然な拡張）をエントロピーを使って証明して、それをaverage-case fine-grained complexityのある数え上げ問題に応用した論文でした。XOR補題は計算量理論では80年代からよく知られている結果で、すでにいくつもの証明方法が知られている（例えば[GNW]が有名）のですが、我々が与えたエントロピーに基づく証明の方が、証明の筋道が直感的にわかり易いのと、（計算量的）疑似エントロピーの良い導入になるので、教育的なのではないかと思っているので、ここで概説します。あくまでも雰囲気がつかめる程度の粒度の記事ですので、細かい詳細は私に直接問い合わせてください（または後日full versionを出すのでそれを参照）。なお、応用についてはここでは省きます。

統計的 vs. 計算量的

平均時計算量という計算量理論の一分野では、情報理論におけるエントロピーなどの概念を「計算量的に」修正したアナロジーを考えることによって、情報理論的な議論に基づいて計算量の結果を証明するということがよく行われます。例えば二つの確率変数$X,Y$の近さを測る指標としてしばし統計距離が使われますが、これは（その確率変数の台を$\Omega$として）

\[
d_{TV}(X,Y)=\max_{D\colon \Omega\to\{0,1\}} \left\{|\Pr[D(X)=1] - \Pr[D(Y)=1]|\right\}
\]
によって定義されます（本来は分布に対して定義されるが、ここでは利便性のため、その分布に従ってサンプリングされた確率変数に対して距離を考えることにする）。ここでは簡単のため$\Omega$は有限集合としています。このとき考える関数$D$を識別者と呼びます。気持ちとしては、識別者は

「与えられた値は$X$と$Y$どちらからサンプリングされたものですか？」

という問題を解こうと頑張っており、その精度の限界値が統計距離となります。すなわち、統計距離が小さいということは、任意の識別者にとって$X$と$Y$が識別できないということになるので、この性質を統計的な識別不可能性（または情報理論的な識別不可能性）と呼びます。

さて、統計距離の定義で考える識別者とは任意の関数を考えていますが、これを

限定的な計算能力を持つ識別者のクラス

に制限することによって新たな識別不可能性の概念を考えることができます。例えば「任意の多項式時間アルゴリズムにとって一様ランダムな文字列と識別できない」といった議論が展開できるわけですが、これを計算量的な識別不可能性と呼び、特に一様ランダムと計算的に識別不可能であるという性質を計算量的疑似ランダムネスと呼びます。

情報理論的には、データ処理不等式により、任意の決定的な関数$f\colon \{0,1\}^n\to\{0,1\}$に対して、分布 $(U_n, f(U_n))$ のエントロピー（ここで$U_n$は$n$ビットの一様ランダムな文字列）は元のランダムシードのエントロピーと一致して必ず$n$のままになる（つまり、決定的な作用を施してもエントロピーは増えない）のですが、計算量理論的な枠組みではある種の計算困難性を仮定すると（計算量理論的）エントロピーを増大できる、という驚くべき結果が知られています。

証明は以前の記事に譲るとして、もう少し深掘りすると、関数$f\colon\{0,1\}^n\to\{0,1\}$が強い平均時困難性を持つとは、任意の効率的な乱択アルゴリズム（注：厳密には非一様なアルゴリズムを考えている）$A$に対して
\[
\Pr_{x\sim U_n,A}[A(x)=f(x)] \le \frac{1}{2} + \varepsilon
\]
を満たすことを言います（$\varepsilon$は文脈依存だがとにかく小さい値。とりあえず$1/\mathrm{poly}(n)$だと思えばよい）。例えば$A$として、$0$ or $1$をランダムに出力するアルゴリズムを考えると正しく$A(x)=f(x)$になる確率はぴったり$1/2$になるわけですが、非自明な精度で$f(x)$を推定しようとすると、その計算能力はすごく沢山要する、というわけです。一方で、右辺が$1$に近い、すなわち
\[
\Pr_{x\sim U_n,A}[A(x)=f(x)] \le 1 - \delta
\]
を満たすとき、弱い平均時困難性を持つと言います。

さて、強い平均時困難性を持つ$f$に対して
\[
(U_n,f(U_n))
\]
という$n+1$ビットの文字列は計算量的疑似ランダムであることが知られており、その逆も成り立ちます。すなわち、関数の計算困難性を計算量的疑似ランダム性で特徴づけられます。例えばNisan-Wigderson生成器を使うと（ある計算量下界の仮定の下での）脱乱択化ができるといった応用があります。

XOR補題

YaoのXOR補題とは、一方向性関数の文脈でYao(1982)で提示された（のちにLevin(1985)で証明が与えられた）結果です。簡単にいうと、弱い平均時困難性を持つ関数 $f\colon \{0,1\}^n\to\{0,1\}$ に対して、別の関数$f^{\oplus k}\colon\{0,1\}^{kn}\to\{0,1\}$を

\[
f^{\oplus k}(x_1,\dots,x_k) = f(x_1) \oplus \dots \oplus f(x_k)
\]

と定義したとき、この関数は（十分大きな$k$に対して）強い平均時困難性を持つ、という結果です。ですので、弱い困難性を持つ関数の下でも、XORをとることでその困難性を増幅させることで、脱乱択といった応用にあてはめることができるようになります。

冒頭でも述べたように、XOR補題の証明は色々知られていて

• 直積定理＋Goldreich-Levin
• hardcore補題
• isolation lemma (Levinによる証明）

などが知られています。本記事で説明する別アプローチの証明は、ZhengのD論(2014)で証明された弱い平均時困難性の計算量的疑似平均最小エントロピー (pseudo average min-entropy)による特徴づけ(PAME theorem)を用います。

疑似（最小）エントロピーとXOR補題

関数 $f$ の強い平均時困難性は疑似ランダム性で特徴づけられると述べましたが、弱い困難性は最小エントロピーの言葉で特徴づけることができます。弱い困難性を持つ関数 $f\colon \{0,1\}^n\to\{0,1\}$ に対して

\[
f(U_n)
\]

という確率変数を考えます。この平均時困難性は、$U_n$が与えられても計算能力が制限された識別者にとっては$f(U_n)$の値が類推できない、すなわちランダムに見えることを保証します。もし$f$が弱い困難性を持つとき、ある程度の精度で類推できるものの、ある程度の確率で間違えます。これを、「$f(U_n)$はある程度のエントロピーを持つ」と解釈します。このエントロピーを疑似エントロピーと呼びます。

もう少しちゃんと述べると、関数 $f$ が疑似エントロピー $\theta$ を持つとは、ある確率変数の組 $(U_n,Z)$ が存在して、

• $(U_n, f(U_n))$ と $(U_n, Z)$ が計算量的に識別不可能
• 条件付き最小エントロピーが$H_{\mathrm{min}}(Z|U_n) \ge \theta$

を満たすことを言います。文脈によってShannonエントロピーを考えることも多いのですが、ここではminエントロピーを考えます（両者の差分については踏み込まないので、詳しくない読者はとりあえず「エントロピーがある」程度の認識で大丈夫です）。

もしも$Z$が一様ランダムなビットだったら疑似ランダム性を持つということになるのですが、この定性的な主張をエントロピーを使って定量的な主張にできます：

定理（Zheng (2014),  informal)

関数 $f\colon \{0,1\}^n\to\{0,1\}$ が弱い困難性を持つ $\iff$ $f$が疑似エントロピー $\log_2 \frac{1}{1-\delta}$ を持つ。

この定理の証明はZhengのD論に書いてあります（私は咀嚼でかなり苦労しました）。この結果は文脈としては[VZ]による、一方向性関数に基づく疑似ランダム生成器の構成の文脈で与えられた結果です（本当は彼らはKL困難性というちょっと異なる概念を考えているが、ほぼ同じ証明でZheng (2014)の結果が示せる）。

ひとまずこの特徴づけを用いると、XOR補題を以下のような流れで証明できます：

1. $f$が弱い困難性を持つので、特徴づけより疑似エントロピーを持つ。
2. $x_1,\dots,x_k \sim U_n$ を独立に選ぶと、$f(x_1),\dots,f(x_k)$はそれぞれ独立でしかも各は$\log_2 \frac{1}{1-\delta}$ の疑似エントロピーを持つ。
3. 情報理論的な議論（本当はフーリエ解析）によって、エントロピーを持つ独立な確率変数の和 $\bmod 2$ はエントロピーが増大する。
4. $k$が十分大きいときはエントロピーはほぼ最大値$1$になる。すなわち$f^{\oplus k}(x_1,\dots,x_k)$は疑似ランダムなので、$f^{\oplus k}$ は強い困難性を持つ。

XOR補題の拡張

XOR補題ではBoolean関数 $f\colon\{0,1\}^n\to\{0,1\}$を考えており、和をとることでBooleanであることを保証するために$\mathbb{F}_2$上での演算を考えていました。我々の論文ではこれを$\mathbb{F}_p$値をとる関数$f\colon\{0,1\}^n\to\mathbb{F}_p$に拡張しました（ただし$p$は素数）。

議論は上のステップ1から4のままです。実はZheng(2014)の結果は$f$がBooleanでなくても成り立つ結果であることを利用します。$p$が素数であるという条件はステップ3において本質で、合成数だと一般には成り立ちません（例えば$\bmod 4$だと、$\{0,2\}$上一様ランダムな確率変数をいくつ足してもエントロピーは変わらない）。

なお、これまで知られているXOR補題の証明はBoolean関数であることを利用しており、例えばhardcore補題ではboostingのために多数決をとるという操作がありますがここでBoolean関数であることを本質的に利用してます（実はZheng (2014)の結果はhardcore補題の拡張とみなすことができます）。Goldreich-Levinは$\mathbb{F}_2$上のHadamard符号のリスト復号アルゴリズムですが、これを$\mathbb{F}_p$に拡張したリスト復号アルゴリズム（[GRS])を用いると、少し異なる主張になってしまいます。

埋め込みクリーク問題

与えられたグラフ$G=(V,E)$に含まれる最大クリークを求めよという問題はKarp's 21 Complete Problemの一つであり, おそらく最も有名なNP困難な問題の一つとして知られています. 本記事ではこの問題の平均時困難性について考えます. すなわち, 与えられたグラフがErdos-Renyiランダムグラフ$G(n,1/2)$のときの最大クリーク(を見つける問題)について紹介し, 関連問題として埋め込みクリーク問題を紹介します.

ランダムグラフ上の最大クリーク問題

Erdős--Rényiグラフ$G(n,1/2)$を考えます. このグラフは$n$個の頂点からなり, 各頂点のペアは独立に確率$1/2$で辺を持ちます. 言い換えれば, $n$頂点の頂点ラベル付きグラフの中から一様ランダムに選ばれたグラフが$G(n,1/2)$です. このように, 入力がランダムに生成された時に問題が効率的に解けるかどうかを議論する枠組みを平均時計算量といいます.

最大クリーク問題に戻りましょう. Erdős--Rényiグラフ$G(n,1/2)$は高確率でおよそサイズ$2\log_2 n$のクリークを持つことが示せます. ここでは厳密な証明はしませんが, なぜ$2\log_2 n$という値が出るかについて, $k$-クリークの個数の期待値を使って簡単に説明します. グラフ$G(n,1/2)$に含まれる$k$-クリークの個数を$X_k$とします. $X_k>0$ならば最大クリークのサイズは$k$以上であり, $X_k=0$ならば$k$未満となります. 頂点部分集合$S\subseteq[n]$に対し, $S$がクリークであるかどうかのindicatorを$X_S$とします. すなわち$S$が$G(n,1/2)$内でクリークになっているならば$X_S=1$, そうでなければ$X_S=0$です. 固定した$S$に対して$X_S=1$となる確率は$(1/2)^{\binom{|S|}{2}}$です. さて, $X_k = \sum_{S\subseteq[n],|S|=k} X_S$ と書けます. 期待値の線形性より, $X_k$の期待値は
\begin{align*}
\mathbb{E}[X_k] &= \sum_{S\subseteq[n],|S|=k} \Pr[X_S=1] \\
&= \binom{n}{k}\cdot 2^{-\binom{k}{2}} \\
&\approx \frac{n^k}{k!} 2^{-k^2/2} \\
&\approx 2^{-k\log_2 n - k^2/2} \\
&\approx 2^{-k(\log_2 n - k/2)}
\end{align*}
となります. 途中で突然$k!$が消えたのは, $k!=2^{(1-o(1))\cdot k\log k}$は$2^{-\binom{k}{2}}$に比べて無視できるほど小さいからです. $k\gg \log_2 n$ならば指数部が負となり$X_k$の期待値は非常に$0$に近い値となります. $k\ll \log_2 n$ならば期待値は非常に大きい値となるので, $G(n,1/2)$は$k$-クリークを含むだろうことがわかります. 前半の議論(非存在性)はMarkovの不等式, 後半の議論(存在性)はChebyshevの不等式を使うと厳密な議論にできます. 詳しく知りたい方はこちらの記事を参照してください.

すなわち, 入力が$G(n,1/2)$だと最大クリークのサイズはおよそ$2\log_2 n$であることがわかります. では, この$2\log_2 n$-クリークを見つけられるでしょうか?

成功確率の枠組み

そもそも「ランダムグラフ上で問題を解く」とはどういうことなのでしょうか?

最悪時計算量の枠組みでは, 「全ての入力に対して正しい答えを出力する」効率的なアルゴリズムの構成が焦点になっていました. 一方で平均時計算量では「全ての入力に対して」という部分を「多くの入力に対して」に緩和した枠組みを考えます. 本当はerrorless/error-proneの二つの概念があるのですが, ここではerror-proneの枠組みを考えます.

定義 (成功確率)

決定的アルゴリズム$A$は以下を満たすとき, 成功確率$\gamma$で$G(n,1/2)$上で最大クリークを解くという:
\begin{align*}
\Pr_{G \sim G(n,1/2)} [ A(G) \text{ outputs a maximum clique in }G]\ge \gamma.
\end{align*}

$A$が乱択アルゴリズムのとき, 上の確率において入力$G\sim G(n,1/2)$および$A$の内部のランダムネスについての確率をとることで成功確率を定義する.

直感的に言えば成功確率とはアルゴリズム$A$が解く(固定サイズの)入力の割合を意味します. 平均時計算量の理論では, 効率的(例えば多項式時間)なアルゴリズムの中で最大の成功確率$\gamma$をもつものが研究の対象となります.

入力によって解けるか解けないかが決まるので, 乱択アルゴリズムのように
「繰り返して成功確率を増幅させる」ことはできない.

例えば, 成功確率$\gamma=1$のアルゴリズムは最悪時の意味において最大クリーク問題を解くことを意味します. これはNP困難なので, $\gamma=1$を満たす多項式時間アルゴリズムは存在しないと広く信じられています. 従って$\gamma<1$の範囲で考えます. この記事では確率$1-o(1)$を「高確率」と呼ぶことにします(注1).

(注1). 「高確率」という言葉は専門用語として扱われることが多いです. ランダムグラフの文脈では漸近的に確率$1$で成り立つことを「a.a.s. (asymptotically almost surely)」「w.h.p. (with high probability)」と言うことがあります. また, 乱択アルゴリズムの文脈では, 何らかの定数$c>0$が存在して確率$1-n^{-c}$で成り立つことを「高確率」ということもあります.

上の定義では誤った答えを出力しうるものの常に多項式時間で終了するアルゴリズムを考えていました. このようにアルゴリズムの「誤りうる」という性質をerror-proneと言います. 一方で, 常に正しい答えを出力するが入力によっては指数時間かかりうるという性質をerrorlessといいます. 乱択アルゴリズムの文脈で例えるとラスヴェガス法か, モンテカルロ法かという話です. 

最悪時と平均時のギャップ

さて, $G(n,1/2)$上での最大クリーク問題に話を戻しましょう. 証明はしませんが, $G(n,1/2)$は確率$1-n^{-\Omega(\log n)}$で最大クリークのサイズが高々$2.01\log_2 n$であることが証明できます. 従って, サイズ$2.01\log_2 n$以下の頂点部分集合$S \subseteq [n]$ を全て列挙し, クリークをなした$S$の中で最大のものを出力すると, $n^{O(\log n)}$時間で成功確率$1-n^{-\Omega(\log n)}$で$G(n,1/2)$上で最大クリークを解けます.

最悪時の世界では最大クリーク問題はETH(強指数時間仮説)の下では$2^{\Omega(n)}$時間かかると予想されていますが, 平均時の世界では単純なbrute-forceを考えれば$n^{O(\log n)}$時間で高確率で解くことができます.

貪欲法

最大クリーク問題に対する最も単純なアプローチが貪欲法です. 何でも良いので極大クリークを一つ選び, 出力するというアルゴリズムです. 例えばクリークに追加できる頂点のうち, インデックスが一番若い頂点を選んで追加するというルールを考えてみましょう.

定理 (Karp, 1976, informal).

入力$G(n,1/2)$上の貪欲法で得られる極大クリークを$S$とすると, 確率$1-o(1)$で$|S| = (1\pm o(1))\log_2 n$を満たす.

すなわち, 貪欲法は"ほぼ2近似"アルゴリズムであるといえます. 最悪時の世界では, 任意の小さな定数$c>0$に対して最大クリークを多項式時間で$n^{1-c}$近似するのはNP困難であることが知られているので, この定理もまた最悪時と平均時の世界のギャップを意味します.

証明(の概要).
貪欲法の$t$回目の反復で得られる頂点部分集合を$S_t$とします. すなわち, $S_0=\emptyset$であり, $S_{t+1}$は$S_t\cup \{u\}$がクリークになるような頂点$u$のうち最もインデックスが若いものとします (例えば一番最初に追加される頂点は必然的に最もインデックスの若い$v_1$になります). $S_t$の要素数は$t$なので, 貪欲法が終了したときのステップ数$t$の上下界を求めればよいことになります.

この「若い頂点を優先する」貪欲法は, 頂点を$v_1,\dots,v_n$の順に見ていき初めて追加できる頂点を見つけたらそれを追加するというように実装することができます. この実装では, 例えば時刻$t$で頂点$v_i$が追加されたとすると, その反復までにアルゴリズムは以降の頂点$v_{i+1},\dots,v_n$を見ていないことになります (もちろんこれは実装依存ですが, $v_{i+1},\dots,v_n$を見ないように実装したものと同じ出力を得るので, 見ていないということを仮定できます). すなわち, この反復までの挙動は誘導部分グラフ$G[\{v_1,\dots,v_i\}]$にのみ依存するのであって, $v_{i+1},\dots,v_n$に接続する辺の情報とは独立です. ですので, 頂点$v_{i+1}$を見たとき, その時初めて辺$\{v_{i+1},v_j\}$ ($j=1,\dots,n\}$) に関する入力の情報をサンプルする (つまり, 入力を生成→アルゴリズムの解析, ではなく, アルゴリズムの反復に応じて入力を徐々に生成していく) という確率過程によってアルゴリズムの振る舞いを解析ができます.

時刻$t$における反復において$S_t$の要素数は$t$であり, $S_t$の全ての頂点と隣接している頂点が新たに$S_{t+1}$に加わるわけですが, 固定した頂点$v_j$が追加される確率は$(1/2)^t$です. 従って, 任意の定数$c>0$に対し$t\ge (1+c)\log_2 n$ならば, $v_j \in [n]$に関するunion boundより一つも頂点が追加されないので, $t \le (1+c)\log_2 n$を得ます. 逆に, $t<(1-c)\log_2 n$ならばこの確率は$n^{-1+c}$となり, 追加できる頂点の個数の期待値はおよそ$n^c$で非常に大きいので, そのような頂点は高確率で存在することになります.

$v_j$は$S_t$の全ての頂点と隣接していればクリークに追加できる.

(証明終)

衝撃的なことに, 本質的に貪欲法より良い多項式時間アルゴリズムはいまだに知られていません (それどころか存在しないと予想されています). 具体的には, 以下の主張が正しいかどうかは非常に重要な未解決問題です.

ある定数$\varepsilon>0$と多項式時間アルゴリズムが存在して, $G(n,1/2)$上で$(1+\varepsilon)\log_2 n$-クリークを確率$2/3$で見つける.

埋め込みクリーク問題

Erdős--Rényiグラフ$G(n,1/2)$上の最大クリーク問題の変種として, $k$-クリークが埋め込まれたランダムグラフから$k$-クリークを復元する問題を考えます. 具体的には, 入力として次の操作によって得られるランダムグラフ$G(n,k,1/2)$が与えられます:

1. Erdős–Rényiグラフ $G(n,1/2)$を生成する, ランダムに$k$個の頂点$v_1,\dots,v_k$を選び, $C=\{v_1,\dots,v_k\}$とする.
2. 各$1\leq i<j\leq k$に対して辺$\{v_i,v_j\}$を追加して$C$をクリークにする (元々$\{v_i,v_j\}$が辺をなす場合は追加しない).

ここで埋め込むクリークサイズ$k$は$k \gg \log n$とします. Erdős--Rényiグラフ$G(n,1/2)$はサイズが$O(\log n)$のクリークを持つので, 直感的にはサイズ$k$のクリークをランダムに埋め込むと一意になる気がします.

最大クリークのときと同様に, アルゴリズムの成功確率を以下のように定義します.

定義 (成功確率)

決定的アルゴリズム$A$は以下を満たすとき, $G(n,k,1/2)$上で成功確率$\gamma$で埋め込みクリーク問題を復元するという:
\begin{align*}
\Pr_{G \sim G(n,k,1/2)} [ A(G,k) \text{ outputs the planted $k$-clique $C$ in }G]\ge \gamma.
\end{align*}

ここでは, 簡単のため, アルゴリズム$A$はクリークサイズ$k$知っていると仮定する.

$A$が乱択アルゴリズムのとき, 上の確率において入力$G\sim G(n,k,1/2)$および$A$の内部のランダムネスについての確率をとることで成功確率を定義する.

情報理論と計算量理論のギャップ

例えば$k=2$の場合はただの辺が埋め込まれただけなので, ランダムな辺を出力するしかできないので情報理論的に成功確率の上回は$O(1/n^2)$となります. 一方で任意の定数$c>0$に対し, $k\ge (2+c)\log_2 n$のとき, $G(n,k,1/2)$は確率$1-2kn 2^{-k/2}$で$k$クリークを一つだけ含むことが初等的な数え上げで示すことができます. このとき, 全探索によって高確率で埋め込んだクリークを復元できます.

実は, $G(n,1/2,k)$上でも$k\ge (2+c)\log_2 n$であれば ($k=n^{0.1}$とかであっても), $n^{O(\log n)}$時間で$k$-クリークを確率$1-o(1)$で解くことができます. 一方で$k \le 2\log_2 n$のときはErdős--Rényiグラフ$G(n,1/2)$は$2\log_2 n$クリークを持つので情報理論的に埋め込まれた$k$-クリーク$C$を復元することはできません.

命題.

任意の定数$c > 0$および$k\ge (2+c)\log_2 n$に対し, $G(n,1/2,k)$上で成功確率$1-o(1)$で埋め込みクリーク問題を解く$n^{O(\log n)}$時間アルゴリズムが存在する. 

証明.

アルゴリズムは非常にシンプルです: サイズ$2\log_2 n$の頂点部分集合$S \subseteq V$を列挙し, もしも$S$が$G(n,1/2,k)$においてクリークをなすならば貪欲法によって極大クリークを一つ選び, そのサイズが$k$と等しいならばその極大クリークを出力する. 最終的にサイズ$k$のクリークが見つからなかったら特別な記号$\bot$ (見つからなかった, を意味する)を出力する.

列挙した各$S$に対して一つの極大クリークしか考えないので計算時間は$n^{O(\log n)}$です. あとはこれで「取りこぼしがない」ことを証明する必要があります. $C$を埋め込まれたクリークとします. 列挙したときにある$S \subseteq C
$に対して, $C$以外の頂点が貪欲法で追加され得ないことを示せばよいです. フォーマルに言うと, ある$S\subseteq C,|S|=2\log_2 n$が存在して, $C$の外側の頂点$v$であって$\Gamma(v) \supseteq S$を満たすものがないことを示せば, $V\setminus C$の頂点が貪欲法で追加され得ないため必ず極大クリークは$C$になります.

こうなるような$S$の存在性を示したい.

埋め込む位置$C$と$V\setminus C$の間の辺は全て独立なコイントスによって決まります. そこで固定した$C$で条件つけたときに所望の$S\subseteq C$が高確率で存在することが言い, その後に$C \sim \binom{[n]}{k}$に関する期待値をとれば$G(n,1/2,k)$上の確率を抑えたことになります.

固定した$C\subseteq [n]$に対し, $S\subseteq V$を$C$内からインデックスの若い$2\log_2 n$個の頂点からなる集合とします. $C$は固定されているため$S$もまた固定されています. 従って, 各$v \in V \setminus C$について$v$が$S$の全ての頂点に隣接している確率は$(1/2)^{2\log_2 n}\le n^{-2}$です (これは$S$が固定されているため, $S$の情報と辺の有無の情報が独立だから成り立つ). $v$についてのunion boundより, 確率$1-O(n^{-2})$で$\Gamma(v)\supseteq S$を満たす$v \in V\setminus C$は存在しません. すなわち, この$S$の構成は高確率で所望の性質を満たします. なお, この議論は$\log_2 n$の係数が$1$より真に大きければ同様に適用できます.

以上より, $G(n,1/2,k)$において, 埋め込んだクリーク$C$の中からインデックスの若い順に$2\log_2 n$個の頂点集合を$S$とすれば, $S$を含む極大クリークは$C$のみになりますので, 確かに列挙するアルゴリズムは埋め込みクリークを解きます. (証明終)

ここまでで単純な列挙によって$n^{O(\log n)}$時間で埋め込みクリーク問題は$k\ge 2.01\log_2 n$ならば高確率で解けることを確認し, $k\le 2\log_2 n$では情報論的に解けないことを見てきました. これは$k=2\log_2 n$が情報理論的に解けるかどうかの境界になっていると解釈できます. では, 同様の範囲の$k$で埋め込みクリーク問題を多項式時間で解けるでしょうか?

結論から言うと$k\ge \sqrt{n}$であれば確率$1-o(1)$で埋め込みクリーク問題は多項式時間で解けることが知られている[Alon, Krivelevich, Sudakov, '98]のですが, $k = o(\sqrt{n})$に対して多項式時間で解けるかどうかは30年来の未解決問題で, 実はある$c>0$に対して$k=n^{1/2-c}$に対して多項式時間で確率$2/3$で埋め込みクリーク問題を解く多項式時間アルゴリズムは存在しないのではないかと予想されています (埋め込みクリーク予想).

ここではAlonらの結果より少し弱い, $k\ge 10\sqrt{n\log n}$のときに埋め込みクリーク問題を解くアルゴリズム[Kučera, 95]を紹介します.

命題.

$k\ge 10\sqrt{n\log n}$のとき, $G(n,1/2,k)$上の埋め込みクリーク問題を高確率で解く多項式時間アルゴリズムが存在する.

証明 (概要).

アルゴリズムは「次数の大きい順に頂点を$k$個出力する」です. 埋め込まれたクリーク$C$に属する頂点は, クリークの分だけ次数が大きくなるはずであり, $k\ge 10\sqrt{n\log n}$ならばその差が有意であるという議論をします.

頂点$v \not\in C$の次数の周辺分布は二項分布$\mathrm{Bin}(n,1/2)$なので, Hoeffdingの不等式および$v$に関するunion boundより
\begin{align*}
\Pr[\exists v\not\in C,\deg(v) > n/2 + \sqrt{n\log n}] \le n\cdot \exp(-2\log n) \le n^{-1}
\end{align*}

を得ます. 一方, $v\in C$の次数の周辺分布は$k+\mathrm{Bin}(n-k,1/2)$なので, 同様にHoeffdingの不等式より, 任意の$t>0$に対し

\begin{align*}
\Pr\left[\exists v\in C,\deg(v) < \frac{n-k}{2}+k-t\right] \le n\exp\left(-\frac{2t^2}{n}\right).
\end{align*}

特に$t=4\sqrt{n\log n}$を代入すると, 確率$1-o(1)$で全ての$v\in C$は$\deg(v) \ge \frac{n}{2} + \sqrt{n\log n}$を満たします. 従って$k\ge 10\sqrt{n\log n}$のとき確かに次数を見ることで$C$が復元できます. (証明終)

Appendix. 埋め込みクリークの一意性

ランダムグラフ$G(n,k,1/2)$は埋め込まれたものが一つあるので, $k$クリークを一つ以上部分グラフとして含みます. ここでは$k\ge (2+c)\log_2 n$の場合は高確率で$k$クリークが一つであることを証明します.

この主張は直感的には自明に思えます. Erdős--Rényiグラフ$G(n,1/2)$の最大クリークは$2\log_2 n$なので, それより大きい$k$-クリークを埋め込むと確かに埋め込まれたクリーク以外に$k$-クリークは登場しなさそうです. ところが, $k$-クリークを埋め込むことによって非自明に大きいクリークが発生しうる懸念をケアしなければなりません.

$G(n,1/2,k)$における他のクリークのサイズはどのくらいになるのでしょうか? 埋め込まれたクリークを表す頂点部分集合を$C$とします. 任意の頂点$v \not \in C$は$C$内におおよそ$k/2$個の隣接点を持ちます.

これは, $v$と$C$の間の辺は独立に確率$1/2$で生起するので, $\Gamma(v)$を$v$の隣接点の頂点集合とすると, $|\Gamma(v) \cap C|$の周辺分布は$\mathrm{Bin}(k,1/2)$になり, これにHoeffdingの不等式を適用することでわかります (より詳しくいうと, 確率$1-n^{-100}$で, 全ての頂点$v$に対し$|\Gamma(v) \cap C| \le k/2 + 100\sqrt{k\log n}$がいえる.)

また, $\{v\} \cup \Gamma(v)$は$G(n,k,1/2)$内でクリークをなすので, $C$以外にも$k/2$-クリークを持つことがわかります. 実は$C$以外のクリークのサイズは全て$k/2 + O(\sqrt{k\log n}) \approx (1+o(1))k/2$以下になります.

この議論に基づくと, $k\ge 100\log_2 n$に対して$k$-クリークの一意性が証明できます (特に, Hoeffdingの不等式でネイピア数が出てくるのでlogの底に関して慎重にならなければなりません). $k\ge (2+c)\log_2 n$に対して一意性を示すにはもう少し丁寧な議論が必要です.

命題 [Theorem 4, Jerrum '92]. 任意の$k$に対して, $G(n,k,1/2)$が二つ以上の$k$クリークを含む確率は高々$2kn2^{-k/2}$である.

証明 (概要).

$V=[n]$を頂点集合, $C\subseteq V$を埋め込まれた$k$クリークとします. $C$とは別の$k$-クリーク$C' \neq C$の個数を$X$とし, その期待値を考えます. すなわち
\begin{align*}
\mathbb{E} = \sum_{C'\in \binom{V}{k},C'\neq C} \Pr[C'\text{ is a $k$-clique}]
\end{align*}

を上から抑えます. 各$t=0,1,\dots,k-1$に対し, $|C'\cap C|=t$なる$C'$を列挙して$t$に関する和を考えると

期待値$\mathbb{E}[X]$は
\begin{align*}
\mathbb{E}[X] &= \sum_{t=0}^{k-1} \binom{k}{t}\binom{n-k}{k-t}\cdot 2^{-\binom{k}{2} + \binom{t}{2}} \\
&\le \sum_{t=0}^{k-1} \left(kn 2^{-k/2}\right)^{k-t} \\
&\le kn 2^{-k/2} \cdot \sum_{t=0}^\infty (1/2)^t \\
&\le 2kn 2^{-k/2}
\end{align*}
を得ます.

確率論的手法の計算論的な複雑性 (大雑把なサーベイ)

組合せ論や計算量理論ではしばし, 良い性質を持った離散構造の存在性が議論されます. 例えば

• 疎な正則エクスパンダーグラフ
• girthと彩色数が無限に大きくなるグラフ
• ランダム抽出器 (randomness extractor)
• 困難な真理値表 (hard truthtable)
• rigid matrix
• universal transversal sequence
• 大きい素数
• discrepancyの小さな部分彩色
• quasi-random graph
• Lovász local lemma
• 多変数多項式の根

といった離散構造はそれ自体が興味の対象となるだけではなく非常に幅広い応用をもち, 擬似ランダム生成器, 良い性質を持つ誤り訂正符号, 計算量下界の証明, 脱乱択の証明, 近似アルゴリズムの構成, アルゴリズムの近似率の限界(PCP定理)などに用いられます.

しかしながらこれらの存在性の証明の多くはしばし確率論的手法や鳩の巣原理などに基づいた非構成的な手法もしくは非効率的な構成に基づく証明になっています. 実際の応用では(特に擬似ランダムネスの文脈では)しばし効率的(計算量が小さい)かつ決定的(ランダムネスを使わない)な構成が求められます. これを確率論的手法の脱乱択化と呼ぶことにします. 

確率論的手法の脱乱択化は組合せ論と計算量理論が密接に関連しているとても面白いトピックですので, ここでは非常に大雑把にいくつかのトピックを紹介していきます. なお, この辺りの擬似ランダムネスに関するトピックはVadhanの本に詳しいです.

疎なエクスパンダーグラフ (ラマヌジャングラフ)

頂点数$n$の$d$-正則グラフ$G$を考えます (ただし$n\geq 2, d\geq 3$). 隣接行列$A$の固有値を大きい順に並べて$d=\lambda_1\geq \lambda_2 \geq \dots \geq \lambda_n$とします. すると, 

\[
\lambda_2 \geq 2\sqrt{d-1} - \frac{2\sqrt{d-1}-1}{\lfloor \mathrm{diam}(G)/2\rfloor}
\]

が成り立つことが知られています(Alon-Boppanaの定理). ここで$\mathrm{diam}(G)$はグラフ$G$の直径で, Moore bound (または幅優先探索に基づく議論)により, $\mathrm{diam}(G)=\Omega(\log_{d-1} n)$が成り立ちます. 従って上記のバウンドにより, $d\geq 3$を固定し$n\to\infty$の漸近を考えると$\lambda_2 \geq 2\sqrt{d-1} - O(1/\log n)$となります.

では, このバウンドは(漸近的に)タイトなのでしょうか? 実はこの問いはランダム正則グラフを考えることで簡単に肯定的に解けます. $n$頂点$d$正則グラフ全体の集合から一様ランダムに選んだグラフを$G_{n,d}$と書くと, Friedman(2003)によると, $n\to\infty$の漸近的を考えると, 確率$1-n^{-0.1}$で$G_{n,d}$は

\[
\lambda_2 \leq 2\sqrt{d-1} + O\left(\left(\frac{\log\log n}{\log n}\right)^2\right)
\]

を満たすことが知られています. なので, 無限に多くの$n$について上記を満たす$n$頂点$d$正則グラフがとれるため, $n\to \infty$の漸近においてAlon-Boppanaの定理のバウンドはほぼタイトであることがわかります. ちなみにFriedman(2003)の定理の別証明を与えたという論文も知られています.

しかしながらこの証明は非構成的であるという点で応用向きではありません. スペクトルグラフ理論では, $\lambda_2 \leq 2\sqrt{d-1}$を満たすグラフをラマヌジャングラフと呼びます. ある$d\geq 3$に対して$d$-正則ラマヌジャングラフの列$(G_i)_{i=1,2,\dots}$であって, $G_i$の頂点数が$i\to\infty$で発散するようなものが陽に構成できるか, という問題を考えます. この問題はLubotzky, Phillips, Sarnak (1988)によって解決され, その後も様々な進展を見ています.

• Lubotzky, Phillips, Sarnak (1988)は$p\equiv 1 \bmod 4$を満たす全ての素数$p$に対して$(p+1)$-正則ラマヌジャングラフの列を代数的に構成する方法を与えました. この構成はいわゆるLPSラマヌジャンなどと呼ばれています.
• Morgenstern (1994)はLPSラマヌジャンを$p$がprime powerの場合に拡張しました.
• 全ての$d\geq 3$に対して$d$正則ラマヌジャングラフは存在するのでしょうか?Friedmanの定理によるとランダム正則グラフは$\lambda_2 \leq 2\sqrt{d-1}+o(1)$を満たすことが知られていますが, 厳密にはラマヌジャングラフであるということを意味しません. このように, $\lambda_2\leq 2\sqrt{d-1}+o(1)$を満たすグラフをnear-Ramanujan graphといいます.
• Marcus, Spielman, Srivastava (2015)は上の問いを解決し, 任意の$d\geq 3$に対して$d$正則二部ラマヌジャン(multi)グラフの無限列の存在性を証明しました. 彼らの証明はinterlacing polynomial methodと呼ばれる手法に基づいており, LPSラマヌジャンなどの代数的なアプローチとは根本的に異なっています.
• すぐ後にCohen(2016)はMarcus, Spielman, Srivastavaの証明を構成的に修正し, $n$頂点ラマヌジャングラフを$\mathrm{poly}(n)$時間で構成するアルゴリズムを与えました.

ランダムネス抽出器

平たく言うとランダムネス抽出器(または単に抽出器)とは, ランダムっぽい文字列を受け取ってランダムな文字列を出力する乱択アルゴリズムです. 入力で与えられる文字列の「ランダムっぽさ」はmin-entropy(以下で定義している)によって測り, 出力文字列のランダムネスは一様ランダムな文字列との統計距離(total variation distance)によって測ります. 一般にdata processing inequalityより, どのような決定的なアルゴリズムを考えても分布のエントロピーを増大させることはできないため, ランダム抽出器は乱択アルゴリズムとしています.

定義1 (min-entropy).

確率変数$X$のmin-entropy $H_\infty(X)$を以下で定める:
\begin{align*}
H_\infty (X) = \min_{x\in\mathsf{supp}(X)}\log_2\frac{1}{\Pr[X=x]}.
\end{align*}

通常のShannon entropyは情報量の期待値によって定義されますが, min-entropyでは情報量の最小値を考えます. すなわちmin-entropyの方がworst-caseの情報量を考えていることになります. 二つの確率変数$X,Y$の統計距離を$d_\mathrm{TV}(X,Y)$で表します.

定義2 (ランダムネス抽出器)

以下を満たす関数$\mathrm{Ext}\colon \{0,1\}^m\times\{0,1\}^d\to\{0,1\}^n$を$(k,\epsilon)$-抽出器と呼ぶ: 任意の$H_{\infty}(X)\geq k$を満たす$\{0,1\}^m$上の分布$X$と$\{0,1\}^d$上の一様分布$U_d$に対し, $d_{\mathrm{TV}}\left( \mathrm{Ext}(X,U_d) , U_n \right) \leq \epsilon$.

すなわち, 抽出器とは, $m$ビットのランダムっぽい文字列$X$と$d$ビットの一様ランダムな文字列$U_d$を受け取り, $n$ビットのランダムな文字列を返す関数のことです. 一般に$m,d$は小さい方がよく, $n$は大きい方が良いです. 入力$X$をしばし弱ランダムソースと呼びます.

ランダムな関数を考えると高確率でランダムネス抽出器になっていることが簡単に示せます. すなわち, 各$\mathrm{Ext}(x,r)$の値を$\{0,1\}^n$上の一様ランダムにとってきたとき, $\mathrm{Ext}(\cdot,\cdot)$が抽出器になっている確率は適切なパラメータの下で$1-o(1)$になることが示せます.

ランダムネス抽出器は以下のように二部グラフによって表現することによって組合せ論的な解釈を与えることができ, そこに組合せ論のテクニックが介入する余地があります.

左側の各頂点は弱ランダムソース$X$の入力に対応しており, 右側の各頂点は$\{0,1\}^n$の元に対応します. 頂点$X$からは$2^d$本の辺が出ており, 各辺には$\{0,1\}^d$の元でラベル付けされています. 頂点$X$からラベル$u\in\{0,1\}^d$の辺を辿った先にある右側の頂点が$\mathrm{Ext}(X,u)$になるようにグラフを構成します.

このように二部グラフを構成すると, 抽出器とは以下の性質を持つ二部グラフ$G=(L,R,E)$であると解釈できます:

左側の頂点集合$L$上のmin-entropy$\ge k$であるような任意の分布に従って頂点$X$を選び, そこから$1$ステップだけランダムウォークを行って得られる右側の頂点を$Y\in R$とする. このとき, $Y$は$R$上一様分布に(統計距離の意味で)近い.

特に, エクスパンダーグラフを考えるとある条件下では抽出器になることが知られています. 抽出器についてのサーベイは, 古い論文ですがNisan(1996)に詳しいです.

エクスパンダーグラフなどの組合わせ論的な道具を使った構成のほかにも, 平均時計算量の道具を使って抽出器を構成するという手法も知られています. Trevisan (2001)は非常に賢いアイデアによって, 多くの擬似ランダム生成器の構成が実は抽出器の構成とみなせるということが示しました. 擬似ランダム生成器(pseudorandom generator; PRG)とは短いランダム文字列を受け取って長いランダム文字列を出力するアルゴリズムです. ただし一般に任意のアルゴリズムはエントロピーを増大しないので, PRGの出力は擬似ランダムであるということが求められます. 詳細は以前の記事をご覧ください. 

例えばNisan-Wigderson generator $G^f_{\mathrm{NW}}\colon \{0,1\}^d\to\{0,1\}^n$は, 計算が非常に困難なBoolean関数$f\colon\{0,1\}^\ell\to\{0,1\}$を使って$d$ビットのランダム文字列$U$(いわゆる乱数シード)を$n$ビットのランダム文字列に変換しています. Trevisan (2001)の抽出器では, 弱ランダムシード$x\in\{0,1\}^m$をまず誤り訂正符号で$2^\ell$ビットの文字列に復号化し, この文字列を真理値表として持つ関数をNisan-Wigderson generatorの構成に用いることによって, 抽出器を構成しています.

解析の大雑把な概要:

もしもTrevisan's extractorの出力値が一様ランダム文字列$U_n$から統計的に離れているならば, Nisan-Wigderson generatorのreconstructionの議論により関数$\mathrm{ECC}(x)\colon\{0,1\}^\ell\to\{0,1\}$からハミング距離$1/2-\epsilon$以下の文字列は短い記述を持つ. さらに$\mathrm{ECC}(x)$に対するリスト復号のアルゴリズムを用いれば, 最終的に弱ランダムシード$x$は短い記述を持つ. これはmin-entropyの仮定に反する.

Rigid Matrix

グラフの剛性とは違う文脈で行列のrigidityと呼ばれる概念があります. 直感的には, $M$がrigidであるというのは, $M$の成分をたくさん書き換えなければ低ランクにできない, ということを意味します. 有限体上の行列$M \in \mathbb{F}_q^{n\times n}$のランクを$\mathrm{rank}(M)$と書き, 二つの行列のハミング距離(異なる成分の個数)を$d_{\mathrm{ham}}(\cdot,\cdot)$で定義します. 

定義3 (matrix rigidity)

行列$M\in\mathbb{F}_q^{n\times n}$と自然数$r\leq n$に対し, $R_M(r)$を
\begin{align*}
R_M(r) := \min\{|S|\colon \mathrm{rank}(A+S)\leq r\}
\end{align*}
で定める. ここで, $|S|$は行列$S\in\mathbb{F}_q^{n\times n}$の非ゼロ成分の個数である.

$(n-r)\times (n-r)$首小行列を考えれば任意の行列$M$に対し$R_M(r)\leq (n-r)^2$が簡単に分かります.

各成分を$\mathbb{F}_q$から一様ランダムに選んで得られるランダム行列$M$に対し高確率で$R_M(r)\leq (n-r)^2/\log n$であることが示せます. 実際, ランク$r$以下の行列の個数とハミング距離$\leq s$のボールのサイズを考える数え上げによる議論で示せます.

Rigid matrixの概念はValiant(1977)によって, 線形変換を計算する算術回路のサイズ下界を得るという文脈で導入されました. 大雑把にいうと, Valiant(1977)はrigidな行列に基づく線形変換は超線形サイズの算術回路を要することを証明しており, ランダム行列は高確率でrigidであることを踏まえると, ランダムな線形変換の算術回路複雑性は超線形であることを意味します. この辺りのサーベイについてはLokam(2009)をご覧ください.

線形変換の回路下界自体も重要なトピックで, 例えば高速フーリエ変換は実用的にも重要な線形変換の一つなのでその計算の下界がわかればアルゴリズムの最適性も議論できることになります.

行列のrigidityに関しては次の重要な予想が重要な未解決問題として知られています.

予想 (Valiant, 1977)

ある体$\mathbb{F}_q$, 定数$\delta,\epsilon>0$およびサイズが発散していく陽に構成できる行列の列$(M_n)_{n=1,2,\dots}$が存在して, 十分大きな任意$n\in\mathbb{N}$に対して$R_{M_n}(\epsilon n) \geq n^{1+\delta}$を満たすようにできるか?

現在は$R_M(r)=\Omega\left(\frac{n^2}{r}\log\frac{n}{r}\right)$という下界が知られています(Friedman(1993), Shokrollahi, Spielman, Stemann (1997)).

近年はrigid matrixを計算量の道具を使って(NPオラクルを使って)構成するという手法が開発されました. Alman and Chen (2019)はNPオラクルを用いてrigid matrixを決定的に構成する手法を与えました. この解析は後にrectanglar PCPというアイデアを用いてsimplifyされました (Bhangale, Harsha, Paradise, Tal (2020)). 以下ではrectanglar PCPについてものすごくざっくり説明します.

非決定性機械に対する時間階層定理より, $\mathsf{NTIME}(2^n)\setminus \mathsf{NTIME}(2^n/n)$に属する判定問題$L$が存在します. さらに$\mathsf{NTIME}(2^n)$に対してPCP定理から PCP $\pi$とPCP検証者$V^{\pi}(\cdot)$が得られます. rencangular PCPとはその名の通り, 行列として表現できるPCP $\pi$のことです. ただしPCP検証者はランダムネスを使って行$i$と列$j$を選び, $\pi[i][j]$を見ます. これを定数回繰り返し, 見た証明ビットの内容においじて受理/拒否を決定します. Bhangaleら(2020)はNTIMEで解ける問題に対してある種の性質を満たすrectangular PCPが存在するということを示しています.

PCP定理から, 入力$x$上で元の問題$L$を得くためにはPCP検証者$V^{\pi}(x)$の受理確率を十分な精度で近似できれば良いです. もしrectanglular PCP $\pi$がrigidでないならば, ある低いランク行列$L$にハミング距離の意味で非常に近いはずです. そこで, nondeterministicに$L$の分解$L=R^\top R$をguessします. 実はこの情報を使ってPCP検証者の受理確率を決定的に十分な精度で近似することができます(!!). 実際には受理確率をある行列内に含まれる$1$の個数で表現し, $\pi$の低ランク分解を用いるとその行列もまた低ランク分解できることを示し, 最後に低ランク行列内に含まれる1の個数は高速に数え上げられるという結果(Chan and Williams, 2016)を使い, 最終的に$L$を$\mathsf{NTIME}(2^n/n)$で解けることを主張します. ところがこれは時間階層定理に矛盾するので, rectangular PCP $\pi$はrigidであることが結論づけられます.

その他の話題 (クラスPPAD)

確率論的手法以外にも非構成的な存在性の証明手法はあります. 例えばゲーム理論ではナッシュ均衡の存在性はブラウアーの不動点定理でその存在性が保証されるものの実際にそれを構成しているわけではありません. このような問題を扱うため, 計算量理論ではPPADと呼ばれる計算量クラスが考えられています. ナッシュ均衡の計算やブラウアーの不動点定理における不動点の計算はPPAD完全である, というある種の困難性の結果が知られています (Daskalakis, Goldberg, Papadimitriou, 2009).

まとめ

確率論的手法は興味深い離散構造の存在性を証明できる非常に強力なツールである一方, その離散構造をどのように得るかについては明示的な情報を与えてくれません. それではそれをどのように構成するかに関しては組合せ論や計算量理論で広く研究されており, 驚くほど広い(理論的な)応用を持っています.

hardcore補題を使ったXOR補題の証明

 平均時計算量においてはXOR補題と呼ばれる定理がよく知られています. この分野では脱乱択化や暗号プリミティブの構成への応用を念頭に, 非常に難しい関数をどのように構成するかが研究されています.

関数$f\colon\{0,1\}^n\to\{0,1\}$に対する回路$C$の成功確率$p_{C,f}$を

\begin{align*}
p_{C,f}:= \Pr_{x\sim\{0,1\}^n}[C(x)=f(x)]
\end{align*}

と定めます. ここで, 有限集合$S$に対して$x\sim S$で$x$は$S$上一様分布に選ばれたことを意味します. 任意のサイズ$s$の回路$C\colon\{0,1\}^n\to\{0,1\}$に対してその成功確率が高々$1-\delta$であるとき, 関数$f$はサイズ$s$に対して$\delta$-困難であるといいます. 定数回路(常に$0$を出力, または常に$1$を出力する回路)を使えば成功確率$\geq1/2$を達成するので, 基本的に$\delta\leq1/2$の範囲で考えます. 特に, 小さい$\epsilon>0$に対して$(1/2-\epsilon)$-困難な関数は正解できる入力の個数が下界に近いので非常に困難な関数であるとみなすことができます. XOR補題とは, XORをとることによって関数の困難性を増幅できることを主張する定理です.

定理1 (XOR補題)

関数$f$, パラメータ$k\in\mathbb{N}$に対して関数$f^{\oplus k}\colon \{0,1\}^{nk}\to\{0,1\}$を

\begin{align*}
f^{\oplus k}(x_1,\dots,x_k)=f(x_1)\oplus \dots \oplus f(x_k)
\end{align*}
で定める. $f$がサイズ$O\left(\frac{\log(1/\delta)}{(\epsilon/k)^2}(s+kn)\right)$に対して$\delta$-困難かつ$k\geq \frac{C\log(1/\epsilon)}{\delta^2}$ならば, $f^{\oplus k}$はサイズ$s$に対して$(1/2-\epsilon)$-困難である. ここで$C$は十分大きな定数である.

一般に, 「関数$f$がサイズ$s$に対して$\delta$-困難ならば関数$g$はサイズ$s'$に対して$(1/2-\epsilon)$-困難である」という形の定理を困難性の増幅(hardness amplification)といい, XOR補題はその最も基本的な定理の一つです. 原則として$s'\approx s$であることが望まれます.

本記事ではこの定理を証明します. そのためにhardcore lemmaを使います. 回路$C$の問題$f$に対する入力集合$H\subseteq\{0,1\}^n$上での成功確率を$p_{C,f,H}:=\Pr_{x\sim H}[C(x)=f(x)]$と定義します. ここでは[Impagliazzo (1995)]のパラメータを改善した[Barak, Hardt, Kale (2009)]による以下のhardcore lemmaを用いることにします:

補題1. (hardcore lemma)

サイズ$s$に対して$\delta$-困難な関数を任意にとってきて$f$とすると, ある$|H|\geq\delta 2^n$を満たす集合$H\subseteq \{0,1\}^n$であって, 任意のサイズ$O\left(\frac{\epsilon^2}{\log(1/\delta)}s\right)$の回路$C$に対して$p_{C,f,H}\leq 1/2-\epsilon$を満たすものが存在する.

補題1によって存在性が保証されている集合$H$を$f$のハードコア集合と呼びます. hardcore lemmaの対偶をとると以下の主張を得ます:

補題1'. (hardcore lemma)

任意の$|H|\geq \delta 2^n$を満たす集合$H\subseteq \{0,1\}^n$に対してあるサイズ$s$の回路$C_H$が存在して$\Pr_{x\sim H}[C_H(x) = f(x)]\geq 1/2+\epsilon$を満たすならば, あるサイズ$O\left(\frac{\log(1/\delta)}{\epsilon^2} \cdot s\right)$の回路$C'$が存在して, $\Pr_{x\sim\{0,1\}^n}[C'(x)=f(x)]\geq 1-\delta$.

関数$f\colon \{0,1\}^n\to\{0,1\}$が$\delta$-困難であるならば, 一様ランダムな$x\sim \{0,1\}^n$に対して確率変数$f(s)$は1ビットのベルヌーイ試行$\mathrm{Ber}(\delta)$と区別がつかないということを意味します. ここでベルヌーイ試行$\mathrm{Ber}(\theta)$とは確率$\theta$で$1$, 確率$1-\theta$で$0$を出力する確率変数です. 従って, ハードコア補題は, 直感的には,

$f$が$\delta$-困難ならば, サイズ$|H|\geq \delta$を満たすある入力集合$H\subseteq \{0,1\}^n$が存在して, 一様ランダムな$x\sim H$に対して$f(x)$は1ビットの一様分布$\mathrm{Ber}(1/2)$と(計算論的に)区別がつかない

ということを主張しています. では, 定理1を証明しましょう. まずはアウトラインを述べます. 独立に$x_1,\dots,x_k\sim\{0,1\}^n$をランダムにとって$f^{\oplus k}(x_1,\dots,x_k)$を考えてみましょう. まず, $x_1,\dots,x_k$のうち少なくとも一つが$H$に入っている確率は下から$1-(1-\delta)^k\approx 1-\mathrm{e}^{-\delta k}\approx 1-\epsilon$で抑えられます. 非常に高確率で発生するこの事象で条件つけ, 例えば$x_i\in H$であるとします. このとき, $x_i$の分布は$H$上で一様ランダムです. したがって$f(x_i)$は$\mathrm{Ber}(1/2)$と区別がつきません. ここで確率変数$f(x_1),\dots,f(x_k)$は$x_1,\dots,x_k$が独立なのでこれらもまた独立であり, $f(x_i)$が$\mathrm{Ber}(1/2)$と区別できないので, XORをとった$f^{\oplus k}(x_1,\dots,x_k)$もまた$\mathrm{Ber}(1/2)$と区別できないです (一様ランダムなビットと他のビットのXORをとったらそれもまた一様ランダムなビットになる). すなわち, $f^{\oplus k}(x_1,\dots,x_k)$が$\mathrm{Ber}(1/2)$と区別できず, これは$f^{\oplus k}(x_1,\dots,x_k)$が$(1/2-\epsilon)$-困難であることを意味します (事象の発生確率が$1-\epsilon$なので$\epsilon$程度のロスが発生している).

以上の流れを対偶を使って証明します. 以下, 二つの確率変数$X,Y$に対し, $X\not\approx_c Y$で$X$と$Y$をcomputationalに識別できる (i.e., ある小さい回路$C$が存在して$|\Pr[C(X)=1]-\Pr[C(Y)=1]|$がnon-negligibleに大きい) ことを表すとします. また, $X\approx_s Y$によって, $X$と$Y$はstatisticalの意味で近い (つまりtotal variation distanceが小さい)ことを表すとします. 最後に, $U_k$によって一様ランダムな$k$ビットの文字列を表すとします. 例えば$(U_{nk},f^{\oplus k}(U_{nk}))$と書いた場合は, $x\sim U_{nk}$を一様ランダムにサンプリングして$x=(x_1,\dots,x_k)$に$k$分割して$(x,f^{\oplus k}(x_1,\dots,x_k))$の分布のことを表すものとします (なので分布のランダムネスは$x$の選び方のみです).

1. $f^{\oplus k}(x_1,\dots,x_k)$を成功確率$(1/2+\epsilon)$で計算するサイズ$s$の回路が存在するので, $(U_{nk},f^{\oplus k}(U_{nk}))\not\approx_c (U_{nk},U_1)$.
2. ランダム関数$f_H(x)$を, $x\in H$ならば$f_H(x)=U_1$, $x\not\in H$ならば$f_H(x)=f(x)$と定義する. 情報論的なバウンドによって, $(U_{nk},f_H^{\oplus k}(U_{nk}))\approx_s (U_{nk},U_1)$.
3. 1と2の議論によって, $(U_{nk},f_H^{\oplus k}(U_{nk}))\approx_s U_{nk+1}\not \approx_c (U_{nk},f^{\oplus k}(U_{nk}))$が得られる. 特に, $(U_{nk},f_H^{\oplus k}(U_{nk}))\not\approx_c (U_{nk},f^{\oplus k}(U_{nk}))$.
4. $(U_{nk},f^k(U_{nk})) \not\approx_c (U_{nk},f^k_H(U_{nk}))$を得る (k-wise XORを識別できるので). ここで, $f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$と定義していて, $(U_{nk},f^k(U_{nk}))$とは$(x_1,\dots,x_k)\sim U_{nk}$に対して$(x_1,\dots,x_k,f(x_1),\dots,f(x_k))$によって与えられるものです.
5. ハイブリッド議論(hybrid argument)によって$(x,f(x))\not\approx_c (x,f_H(x))$となる (ただし分布のランダムネスは$x\sim U_n$).
6. $H$が密(i.e., $|H|\geq \delta 2^n$)であることを使うと, $H$上一様ランダムな$x\sim H$に対して$(x,f(x))\not\approx_c (x,f_H(x))=(x,U_1)$が示せる.
7. Yao's next-bit predictorより, $x\sim H$に対して$f(x)$を成功確率$1/2+\epsilon$で計算できる.
8. ハードコア補題より$\{0,1\}^n$上で$f$を成功確率$1-\delta$で計算できる. これは元の$f$の条件に矛盾する.

それでは, 定理1の証明をします. 以下の議論では上記のステップ1〜8を補足しつつフォーマルに確認していくだけなので, 上記のアイデアで満足な人は読まなくても構いません.

関数$f$をサイズ$s$に対して$\delta$-困難な関数とし, $H\subseteq\{0,1\}^n$をハードコア集合とします. 回路$D$のサイズを$\mathrm{size}(D)$と表すことにします.

ステップ1. $f^{\oplus k}(U_{nk})$を成功確率$1/2+\epsilon$で計算する回路を$C$とします. 与えられた$(x,b)\in \{0,1\}^{nk+1}$に対して$C(x)\oplus b \oplus 1$を出力する回路を$C_1$とすると,

\begin{align*}
&\Pr_{x\sim U_{nk}}[C_1(x,f^{\oplus k}(x))=1] = \Pr_x[C(x)=f^{\oplus k}(x)] \geq \frac{1}{2}+\epsilon \\
&\Pr_{x\sim U_{nk},b\sim U_1}[C_1(x,b)=1] = \frac{1}{2}
\end{align*}

より, 二つの分布$(U_{nk},f^{\oplus k}(U_{nk}))$と$(U_{nk},U_1)$を$\epsilon$のアドバンテージで識別できます. $C_1$のサイズは, $\mathrm{size}(C_1) = \mathrm{size}(C)+O(1)$を満たします.

ステップ2. 関数$f_H\colon\{0,1\}^n\to\{0,1\}$を

\begin{align*}f_H(x) = \begin{cases}U_1 & \text{ if }x\in H,\\f(x) & \text{otherwise}\end{cases}\end{align*}

とします. ここで$U_1$は各$x\in H$ごとにランダムに生成されるランダムビットです. 厳密には$\mathcal{F}_H$を, 任意の$x\not\in H$に対して$g(x)=f(x)$を満たす関数$g$の集合, すなわち

\begin{align*}
\mathcal{F}_H = \{g\colon \forall x\not\in H, g(x)=f(x)\}
\end{align*}

と定義したときに$f_H$は$\mathcal{F}_H$から一様ランダムに選ばれたランダム関数として定義されます. 独立に$k$個の入力$x_1,\dots,x_k\sim U_n$と$k$個のランダム関数$f_H$をサンプリングして, $f_H(x_i)$のXORをとったときの値$f_H^{\oplus k}(x_1,\dots,x_k)$の分布を考えましょう (ランダムネスは$x_i$と$f_H$の選び方についてとる). どれか一つの$i$でも$f_H(x_i)=U_1$であったならば, そのXORの値もまた$U_1$となります. 従って, 統計距離は$\prod_{i=1}^k \Pr[x_i\not\in H] \leq (1-\delta)^k$となり (ここで$|H|\geq\delta\cdot 2^n$を使っている), 適当な$k=O(\log(1/\epsilon)/\delta)$に対して統計距離は高々$0.1\epsilon$となります.

ステップ3. 統計距離の性質から, ステップ1で構成された回路$C_1$は二つの分布$(U_{nk},f^{\oplus k}(U_{nk}))$と$(U_{nk},U_1)$をアドバンテージ$0.9\epsilon$で識別します.

ステップ4. 二つの分布$(U_{nk}, f^k(U_{nk}))$と$(U_{nk},f_H^k(U_{nk}))$を識別する回路$C_2$を以下のように構成します: 入力$(x_1,\dots,x_k,b_1,\dots,b_k)$に対し, $C_1(x_1,\dots,x_k,b_1\oplus\dots\oplus b_k)$を出力する. この回路$C_2$は, $C_1$の識別性により確かに二つの分布$(U_{nk}, f^k(U_{nk}))$と$(U_{nk},f_H^k(U_{nk}))$をアドバンテージ$0.9\epsilon$で識別します. 回路$C_2$のサイズは高々$\mathrm{size}(C_1)+O(k)$です.

ステップ5. ステップ4で構成された回路$C_2$は二つの分布
\begin{align*}
&D_0 := (x_1,\dots,x_k,f(x_1),\dots,f(x_k)),\\
&D_k := (x_1,\dots,x_k,f_H(x_1),\dots,f_H(x_k))
\end{align*}
をアドバンテージ$0.9\epsilon$で識別します. これら二つの分布を滑らかに補間するような分布列$D_1,\dots,D_{k-1}$を
\begin{align*}
D_i := (x_1,\dots,x_k,f(x_1),\dots,f(x_{i-1}),f_H(x_i),\dots,f_H(x_k))
\end{align*}
とします(これをハイブリッド分布とよぶ). $i=0,k$の場合でもそれぞれ$D_0,D_k$になっていることが分かります. $p_i = \Pr[C_2(D_i)=1]$とすると, $p_0 - p_k = \sum_{i\in[k]}(p_{i-1} - p_{i}) \geq 0.9\epsilon$なので, ある$i\in[k]$が存在して$p_{i-1} - p_i \geq 0.9\epsilon/k$を満たします. 

さらに, ある$z_1,\dots,z_{i-1},z_{i+1},\dots,z_k \in \{0,1\}^{n}$および$c_1,\dots,c_{i-1},c_{i+1},\dots,c_k\in \{0,1\}$が存在して,

\begin{align*}
\Pr_{x\sim U_n}[C_2(\mathbf{v}(i,x,f(x))=1] - \Pr_{x\sim U_n}[C_2(\mathbf{v}(i,x,f_H(x))]\geq \frac{0.9\epsilon}{k}
\end{align*}
が成り立ちます. ここで, $\mathbf{v}(i,x,b)$は
\begin{align*}
\mathbf{v}(i,x,b) = (z_1,\dots,z_{i-1},x,z_{i+1},\dots,z_k,c_1,\dots,c_{i-1},b,c_{i+1},\dots,c_k)
\end{align*}
で定義される文字列である (インデックス$i$と各$z_j$と$c_j$は入力$x$に依存しない値なので, これらの情報を回路にあらかじめ組み込むことによって, 与えられた$x,b$に対し$\mathbf{v}(i,x,b)$はサイズ$O(kn)$の回路で計算できる). 従って, 関数$(x,b)\mapsto C'(\mathbf{v}(i,x,b))$はサイズ$s+O(nk)$程度で計算でき, さらに上記の式より二つの分布$(x,f(x))$と$(x,f_H(x))$をアドバンテージ$0.9\epsilon/k$で識別する. この回路を$C_3$とします.

ステップ6. 全ての$x\not\in H$に対して定義より$f(x) = f_H(x)$となるので, $(U_n,f(U_n))$と$(U_n,f_H(U_n))$が区別できるということは, ステップ5の回路$C_3$を使って$x\sim H$に対して$(x,f(x))$と$(x,f_H(x))$が区別できるということになります. 実際,
\begin{align*}
\frac{0.9\epsilon}{k} &\leq \Pr[C_3(U_n,f(U_n))=1] - \Pr[C_3(U_n,f_H(U_n))=1] \\ &= 2^{-n}\sum_{x\in\{0,1\}^n} (C_3(x,f(x)) - \mathbb{E}_{f_H}[C_3(x,f_H(x))]) \\ &= 2^{-n}\sum_{x\in H}(C_3(x,f(x)) - \mathbb{E}[C_3(x,U_1)]) & & \text{since $f_H(x)=U_1$ for $x\in H$} \\ &\leq \frac{1}{|H|}\sum_{x\in H}(C_3(x,f(x)) - \mathbb{E}[C_3(x,U_1)]) & & \text{since $f_H(x)=U_1$ for $x\in H$} \\ &= \Pr_{x\sim H}[C_3(x,f(x))=1] - \Pr_{x\sim H,U_1}[C_3(x,U_1)=1]
\end{align*}

なので$C_3$は, $x\sim H$に対して$(x,f(x))$と$(x,U_1)$を識別します.

ステップ7. 以前の記事で紹介した計算量的な識別不可能性の概念を思い起こします. この概念は関数の困難性と等価であることがYao's next-bit predictorからわかります.

定義1.

$\{0,1\}^n$上の二つの確率変数$X,Y$は, あるサイズ$s$の回路$C$が存在して
\begin{align*}
\Pr[C(X)=1]-\Pr[C(Y)=1]\geq \epsilon
\end{align*}

を満たすとき, サイズ$s$で$\epsilon$-識別可能であるといい, $C$を識別回路という. 逆に, そのような回路$C$が存在しない場合はサイズ$s$で$\epsilon$-識別不可能であるという.

補題2 (Yao's next-bit predictor; 以前の記事の定理の対偶の言い換え).

関数$f\colon \{0,1\}^n\to\{0,1\}$に対し, 二つの分布$(U_n,f(U_n))$と$(U_n,U_1)$がサイズ$s$で$\epsilon$-識別可能であるならば, サイズ$s+O(1)$のある回路$C$が存在して

\begin{align*}
\Pr_{x\sim U_n}[C(x) = f(x)] \geq \frac{1}{2} + \epsilon.
\end{align*}

上記の補題において, $U_n$を$H$上の一様分布に置き換えることによって以下の補題を得ます.

補題3.

関数$f\colon \{0,1\}^n\to\{0,1\}$と任意の集合$H\subseteq\{0,1\}^n$を考える. $x\sim H$に対して二つの分布$(x,f(x))$と$(x,U_1)$がサイズ$s$で$\epsilon$-識別可能であるならば, サイズ$s+O(1)$のある回路$C$が存在して
\begin{align*}
\Pr_{x\sim H}[C(x) = f(x)] \geq \frac{1}{2} + \epsilon.
\end{align*}

補題3の証明は省略しますが, $\ell = \lceil \log_2 |H|\rceil$に対して, $H$上の一様分布を$U_\ell$とみなすことができることから分かると思います.

ステップ6までの議論より補題3の仮定を満たす回路が存在するので, あるサイズ$\mathrm{size}(C_3)+O(1) = s+O(nk)$の回路$C_4$が存在して
\begin{align*}
\Pr_{x\sim H}[C_4(x) = f(x)] \geq \frac{1}{2} + \frac{0.9\epsilon}{k}
\end{align*}
が成り立ちます.

ステップ8. ハードコア補題(補題1)の対偶を適用する. 任意の$|H|\geq \delta 2^n$を満たす$H$に対してある回路$C_4$が存在して$p_{C_4,f,H}\geq \frac{1}{2} + \frac{0.9\epsilon}{k}$となるので, 補題1'より, $f$を成功確率$1-\delta$で計算する回路$C_5$であって, サイズ
\[
\mathrm{size}(C_5) = O\left(\frac{\log(1/\delta)}{(\epsilon/k)^2}(s+kn)\right)
\]
となるものが存在する. これは定理1の$f$の困難性の仮定に矛盾します.