講義資料をNotionで書いてみた

 プログラミング応用という名前の講義を受け持っており, そこで組合せ最適化のベーシックな話題とそのPythonでの実装を教えているのですが, 資料をNotionで書いてみました.

講義資料をNotionで公開しているのでアルゴリズムの基礎とかNP困難性とかを勉強したい人はどうぞ.https://t.co/49oRdTTHC8 pic.twitter.com/lU20ymalwy

— Nobutaka Shimizu (@knewknowl) November 26, 2024

ちなみに授業の内容としては, アルゴリズムを教えて演習課題として競技プログラミングのような問題を出題しています. 例えば無向グラフの四角形の有無を, 頂点数 $n$ に対して $O(n^2)$ 時間で判定せよという問題を難問枠で出題しています. これらの問題をipynbファイルで作成し, 学生には google colab などでPythonで実装してもらうという形をとっています. 見た目としてはこんな感じです:

多くの講義では, 各回のLaTeXで作成した講義資料を別々のpdfにして配布するというスタイルをとっています. しかしながらpdfだと

• 他のpdfファイルへのリンクが貼れない (全ての講義資料をまとめて作り, 各回ごとに分割して配布するというやり方もあるが, それだと最初に全て作るのがとても大変)
• この部分のように証明の表示/非表示の切り替えができない (長い証明は一旦読み飛ばし, 資料の大枠を最初に俯瞰したい場合が多々ある)
• アルゴリズムのデモを動画として表示できない
• なんとなくデザインがイケてない (おい)

といった点が個人的に気に入りませんでした. そこで

見た目も良い感じで個人的にはかなり気に入っているのですが, 資料作成を通じて感じたメリット/デメリットを連ねておきます. 講義資料作成の参考になればと思います.

Notionとは?

簡単に言うとイケてる資料をweb上で作成できるサービスです. 私は以前から勉強した内容や論文を書く時のメモに使っています. 実際に講義資料を見てもらえると分かりやすいと思います.

メリットとしては

1. 全体的にイケてる
2. 数式が簡単に埋め込める. LaTeXの記法がそのまま使えるし, $$\begin{align*}...\end{align*}$$ とかもそのまま使える.
3. コールアウトと呼ばれる装飾を使えば, 定理などの主張を簡単に書ける
4. ブロック毎に文を管理しており, それぞれのブロックへのリンクが簡単に貼れるので, 「フォード・ファルカーソン法では実行時間が遅くなる例が存在したが...」といった文が書けます.
5. トグルというブロックを使うことで, この部分のように表示のオン/オフを切り替えることができる.
6. 図や動画がドラッグ＆ドロップで簡単に貼れる.
7. draw.ioからこんな感じで, 自信のPCに保存することなく直接ページに図を埋め込める

このように見ると非常に素晴らしい選択肢のように思えるのですが, 一方でいくつか考えなければならない点をかかえています:

1. そもそもNotionが落ちたら資料が見れなくなる
2. ネットに公開する必要があるので, 公開できない内容は書けない
3. LaTeXのnewcommandとかができない (個人的にこれはかなり痛い)
4. VSCodeで執筆できないのでスニペットとかが使えない (Notionページのビューワーはあるらしい)

講義資料を作る最初の1,2週間は特に気にならなかったのですが, ずっとやってると上記の3と4はかなり辛くなってきました.

あとやはりNotionは重いらしいので, GitHub Pages + Foam とかも試してみようかなと思っています.

Håstadのスイッチング補題

回路計算量の理論における重要な結果の一つである Håstadのスイッチング補題 を紹介します. 簡潔にいうとこの補題は, 99%の変数をランダムに固定することによってDNFの決定木が小さくなることを主張する結果です. 応用としてparity関数に対する$\mathrm{AC}^0$回路 (非有界fan-inをもつ定数段回路のクラス)に対するタイトな下界を証明できます. 証明の本質には決定木が深くなるようなDNFの部分代入は短い長さで記述できる (従ってそのような部分代入の個数は相対的に少ない) というアイデアを使っています.

スイッチング補題は海外の大学に講義資料があり, 本記事もそれらを参考にしました:

• lecture note by O’Donnell … 長いがかなり丁寧.
• lecture note by Jonathan Katz … 証明は短く簡潔. O’Donellの証明の要約
• lecture note by Lovett … 証明はしていないがさまざまな帰結をFourier analysisの視点から紹介

1. 準備

CNF, DNF, 決定木など必要な概念を定義していきます.　ここでは$n$変数の論理関数といえば$\{0,1\}^n \to \{0,1\}$を意味し, true/falseをそれぞれ1/0で表します.

定義1.1 (CNF, DNF).

• 論理変数$\mathrm{x}$に対して, $\mathrm{x}$と$\overline{\mathrm{x}}$をリテラル (literal) と呼ぶ.
• 複数のリテラルを$\lor$で繋げたもの $\ell_1 \lor \dots \lor \ell_w$ を節 (clause) と呼ぶ. 同様に, 複数のリテラルを$\land$で繋げたもの $\ell_1 \land \dots \land \ell_w$ を項 (term) と呼ぶ. このとき, 繋げたリテラルの個数$w$を幅 (width) と呼ぶ.
• 複数の節 $C_1, \dots, C_m$ を $\land$ で繋げた論理式の表現形式を連言標準形 (CNF) と呼ぶ. 同様に, 複数の項 $T_1,\dots,T_m$ を $\lor$ で繋げたものを選言標準形 (DNF) と呼ぶ. この記事ではそれぞれをCNF, DNFと呼ぶことにする.
• 特に, 全ての節 (項) の幅が$w$以下であるCNF (DNF) を$w$-CNF (DNF)という.

ド・モルガンの法則より, CNFの否定をとるとDNFになります. 従って, 本記事ではCNFとDNFはDNFに焦点をあてて説明しますが, 否定をとることによってCNFに変換しても同じことが成り立ちます.

図1. 3-DNFの例

CNFやDNFはあくまでも論理式のフォーマットの一つです. $n$変数の論理式は全部で$2^{2^n}$個あるので, その全てを表現しようとすると$2^n$ビット必要となりますが, 項が$m$個の$w$-DNFは$O(mw\log n)$ビットで表現できるので, $m$と$w$が小さいときのDNFは論理式のコンパクトな表現になっています. 逆に, 任意の論理関数は$2^n$個の項をもつ$n$-DNFで表現できます.

図2. 真理値表からDNFへの変換

定義1.2 (決定木).

次の性質を持つ二分木を決定木 (deceision tree) という:

• 葉には0または1のラベルがついていて, 葉以外の頂点はどれかの変数でラベル付けされている.
• 葉以外の各頂点から子に向かう二本の辺には0または1のラベルがついている.

決定木による計算では, 根から開始して入力に応じて葉に向かって遷移していき, たどり着いた葉のラベルを出力する. 遷移の規則は次のようにして定める: 現在いる頂点のラベルの変数$x_i$に対し $x_i=b \in \{0,1\}$ならばラベル$b$の辺に沿って子に遷移する.

論理関数 $f\colon \{0,1\}^n\to\{0,1\}$と等価な決定木の中での最小の深さを$f$の決定木複雑性と呼び, $\mathsf{DT}(f)$で表す.

図3. 決定木の例.

決定木複雑性が小さい回路は幅の小さいDNFで表現できます.

観察1.3 (決定木$\Rightarrow$DNF).

論理関数$f$が$\mathsf{DT}(f) \le w$を満たすならば, $f$は$w$-DNFで表現できる.

図4. 各1の葉に対し, そこに至るパスに対応する割り当てを1にする項を作る. これらの項をORでつなげればよい.

同様に, 否定を考えることによって, 幅の小さいCNFも構成できます.

任意の$n$-変数の論理関数$f$は全ての変数の割り当てを列挙することによって深さ$n$の決定木で表現できます. これを$f$の自明な決定木と呼ぶことにします. 自明な決定木は深さ$n$の完全平衡二分木です.

2. Håstadのスイッチング補題

Håstadのスイッチング補題は, 幅の小さいDNFの変数をいくつかランダムに選んでランダムに0または1を代入すると決定木複雑性が小さくなるということを主張します. 結果をフォーマルに述べるために, ランダム制限という概念を以下で定義します.

定義2.1 (制限).

パラメータ$n,s\in\mathbb{N}$に対し, $n$変数の$s$-制限 (または部分割り当て) とは関数$\alpha\colon [n] \to \{0,1,\star\}$であって, $s$個の$i\in[n]$に対して$\alpha(i) = \star$を満たすものである. $s$-制限全体の集合を$\mathcal{R}_s$とする (ここでは$n$は固定して考える. $\mathcal{R}$はrestrictionの略). $\mathcal{R}_s$から一様ランダムに選ばれた制限をランダム$s$-制限と呼ぶ.

$s$-制限$\alpha$は部分的に変数に代入を行う操作 ($\alpha(i)=0$ならば$x_i\leftarrow 0$, $\alpha(j)=1$ならば$x_j\leftarrow 1$) として捉える. 変数$x_1,\dots,x_n$をもつ論理関数 $f\colon \{0,1\}^n \to \{0,1\}$ に対してこの部分的な代入操作を行なって得られる$s$変数論理関数を$f|_\alpha$とする.

$s$-制限とは$s$変数関数にするという操作です. ランダム$s$-制限とは, ランダムに$n-s$個の変数を選んで$0$または$1$をランダムに代入するという操作です.

図5. $1$-制限の例.

定理2.2 (スイッチング補題 [Håstad, 1986]).

$w$-DNFで表現される論理関数 $f \colon \{0,1\}^n \to \{0,1\}$ に対するランダム$s$-制限$\alpha$は以下を満たす:
$$\begin{align*} \Pr_\alpha\left[ \mathsf{DT}(f|_\alpha) > d \right] \le \left(\frac{4w s}{n-s} \right)^d \end{align*}$$

冒頭にも述べたとおり, Håstadのスイッチング補題とは幅の小さいDNFの変数をランダムにいくつか選んでランダムに代入操作を施すと, 得られる関数は浅い決定木で表現できるという結果です.

応用の一つとしてparity関数のAC0回路下界の証明にあります. AC0回路とは, 定数段でfan-in (各素子の入次数) が非有界なものです. parity関数とは入力の中の$1$の個数の偶奇を出力する関数です. 

図6. AC0回路のイメージ. 途中の$\neg$素子は省略.

スイッチング補題および観察1.3より, ランダムな制約を考えるとDNFをCNFに変換することができます. これをAC0回路の最下段に適用すると, $\lor$と$\land$の切り替えの回数を一つだけ減らせます. これを定数回だけ繰り返すとAC0回路は最終的には定数関数になってしまいます. 一方でparity関数は$s>0$である限り, どのような$s$-制限を考えても定数関数になりません. この差異によって回路下界を証明するという算段です. 詳細は省略します.

3. スイッチング補題の証明

3.1. 証明の方針

$w$-DNF $f$ の$s$-制限$\beta \in \mathcal{R}_s$ が $\mathsf{DT}(f|_\beta)>d$ を満たすとき, $\beta$はbadであると呼びます. badな$s$-制限の集合を$\mathcal{B}$とし, $|\mathcal{B}|$が小さいことを証明していきます. そのために, DNFのbadな制限は簡潔な記述を持つことを証明します.

フォーマルに述べると, サイズの小さいある集合$\Omega$に対して単射$\varphi \colon \mathcal{B} \to \Omega$を構成することで$|\mathcal{B}|\le |\Omega|$を示します. さらに, $|\Omega| \le \left(\frac{10sw}{n}\right)^d\cdot |\mathcal{R}_s|$ となることを示せたとすると, 所望の確率は

$$\begin{align*} \Pr_\beta\left[ \mathsf{DT}(f|_\beta) > d \right] \le \frac{|\mathcal{B}|}{|\mathcal{R}_s|} \le  \frac{|\Omega|}{|\mathcal{R}_s|} \le \left(\frac{10sw}{n}\right)^d. \end{align*}$$

となり, 主張を得ます.

3.2. 準備

$w$-DNF $f$の各項が順序づけられており, $f=T_1 \lor T_2 \lor \dots T_m$とします. さらに, 各項$T_i$に含まれるリテラルも変数の番号によるデフォルトの順序があるとします. 例えば$T_1=x_1\lor \overline{x_3} \lor x_5$ならば$x_1,x_3,x_5$という順があります.

badの$s$-制限$\beta$に対して$f|_\beta$もまた$w$-DNFであり, これを

$$\begin{align*} f|_\beta = T_{i_1} \lor \dots \lor T_{i_\ell} \end{align*}$$
とします. ここで, $\beta$によって$T_i\equiv 1$となる項が存在すると$f|_\beta\equiv 1$となってしまいbadであることに矛盾してしまいます. 同様に「全ての項が0に固定されてしまう」こともありません. 従って上記のような形で$f|_\beta$を表現できます.

図7. canonicalな決定木の構成.

$f|_\beta$の項$T_{i_1},\dots,T_{i_\ell}$の幅がそれぞれ$d_1,\dots,d_\ell$とします. このとき, canonicalな決定木$\mathcal{T}$を以下で定義します: 先頭の項$T_{i_1}$を$d_1$変数の論理関数とみなしたとき, その自明な決定木を$\mathcal{T}_1$とします. $T_{i_1}$は項なので, 充足割り当てはただ一つしか存在しません. 従ってこの決定木$\mathcal{T}_1$はただ一つの$1$の葉を持っています. この唯一の葉を$\mathcal{T}$における$1$の葉とします. 残りの$2^{d_1}-1$個の$0$の葉に対して, これを根として$T_{i_2}, T_{i_3},\dots$の順で同様の操作を続けていきます. ただし, 固定された変数はそれ以降の項でも固定します. 例えば$\mathcal{T}_1$のある葉において$x_1=0$と固定されている場合は, その葉に続けて構成していく$\mathcal{T}_2,\mathcal{T}_3,\dots$においても常に$x_1=0$として扱います. なお, この固定によって途中で$T_{i_j}$の値が0に固定されてしまった場合はそのままスルーして$T_{i_{j+1}}$に移動します. これは, 例えば$T_{i_1},T_{i_2}$での操作によって$x_1$から$x_5$までの変数が全て固定されていたときに$T_{i_3}$に含まれる変数が$x_2,x_3,x_5$であった場合などに起こりえます.

図8. canonicalな決定木上の長いパス$P$.

部分割り当て$\beta$がbadであるため, このように構成されたcanonicalな決定木$\mathcal{T}$の深さは$d$を超えます. 従って根を始点として子に伝っていく長さ$d$のパスが一つ以上存在します. そのようなパスの中で割り当てが辞書順最小のものを$P$とします. ここで, canonicalな決定木はその構成から, 代入される変数の順番は固定長のパスの中ではどのパスを選んでも同じになります (固定の仕方によっては途中で$1$の葉に行き着く可能性もあるので, パス長は固定して考える). 従って長さ$d$のパスが固定する変数はどれも同じ変数を選ぶため, 辞書順最小な割り当てを持つパス$P$が一意に定まります.

このパス$P$が経由する項を順番に$T_{i_1},\dots,T_{i_k}$とします. パス$P$はちょうど$d$個の変数の値を固定するため, 最後の行$T_{i_k}$は部分的に値が固定される可能性があります.

3.3. badな制限のencoding

図9. badな制限の記述

3.2で定義されたパス$P$が経由する項を$T_{i_1},\dots,T_{i_k}$とします. badな$s$-制限$\beta$の部分割り当てを次のように拡張して得られる$(s-d)$-制限を$\gamma$とします: 制限$\beta$からスタートします. まず, 項$T_{i_1}$に対して$T_{i_1}\equiv 1$となる唯一の割り当て ($T_{i_1}$は項なのでそのような割り当ては一意に存在する) を$\beta$に追加して得られる$(s-d_1)$-制限を$\beta_1$とします. 同様の操作を続いて$T_{i_2},T_{i_3},\dots$に適用していき, $d$個の変数を固定した段階で得られる$(s-d)$-制限を$\gamma$とします (ちょうど$d$個の変数を固定するので, 最後の行はいくつかの変数が未固定になりえます).

図10. $\mathsf{info}$の例. 元の項の何番目の変数に何を代入したかという情報を保持している.

$j$回目の繰り返しにおいて$T_{i_j}$の何番目の変数に何を代入したか, という情報を$j=1$から$k$まで記述した情報$\mathsf{info}$と表すことにします.

各行$T_{i_j}$に含まれるリテラルにはデフォルトの順序がついているので, $\mathsf{info}$の情報を見ると$\beta$と$\gamma$の差分がわかります.

$\Omega$を, $\beta$を動かしたときにありうる$(\gamma, \mathsf{info})$全体の集合とし, 単射$\varphi\colon \mathcal{B}\to \Omega$を
$$\begin{align*} \varphi \colon \beta \mapsto (\gamma,\mathsf{info}) \end{align*}$$
とします. この写像が実際に単射となっていることを確認します. つまり, $(\gamma,\mathsf{info})$から元の$s$-制限$\beta$が復元できることを確認します. この復元操作では, $\beta$を知らず$(\gamma,\mathsf{info})$のみを知っている状態なので, canonicalな決定木$\mathcal{T}$や$\beta$によって固定されない項$T_{i_1},T_{i_2},\dots$や辞書順最小のパス$P$は分からないことに注意してください. なお, 関数$f$はわかっているので$f$の情報 ($T_1,\dots,T_m$) も用いてよいです.

3.4. $(f,\gamma,\mathsf{info})$から$\beta$の復元

方針としては, $\gamma$は$\beta$に追加していくつかの変数に代入を施して得られる部分割り当てです. この「追加して固定した変数は何か」がわかれば$\beta$を復元できます. そこで$\gamma$と$\beta$の違いに着目していきます.

では, 両者の差分はどこに現れるでしょうか? $\beta$はbadな割り当てなので, $f|_\beta$の全ての項は未固定もしくは$0$に固定されます. 一方で$\gamma$は$f|_\beta$の項を先頭から順に$1$になるよう固定することで構成されています.

図11. 復元アルゴリズム.

$w$-DNF $f$のcanonicalな決定木を考えます. ここで考える$f$のcanonicalな決定木とは, 項$T_1,T_2,\dots$の順番で部分木を繋げていき, 各部分木では対応する項に含まれる変数をそのデフォルトの順序で固定していくという決定木です. 決定木を$(s-d)$-制限$\gamma$に沿って辿っていきます. 部分木を通過する際にその部分木の葉のラベルが$0$か$1$かで場合分けをします. 

1. 葉のラベルが$0$のとき

そのまま次の部分木に移動して同様に辿っていきます.

2. 葉のラベルが$1$のとき

この部分木において, $\beta$と$\gamma$の差分が現れています. この差分は$\mathsf{info}$によって取得し, 全てのラベル$0$の葉に対して再び辿っていきます. 具体的には, $\mathsf{info}$の先頭の情報 「$j_1$番目の変数に$b_1$を代入, $j_2$番目の変数に$b_2$を代入, ...」に対し, 項$T_i$の$j_1$番目, $j_2$番目, ... の変数への代入操作を$\gamma$から除去します. さらに, $\mathsf{info}$から先頭の情報を削除します. そして, 部分木の$0$の葉を全て列挙し, それぞれの葉について同様に$\gamma$に沿って部分木を辿っていきます. (復元アルゴリズムの効率性は考慮していません).

これを繰り返し, $\gamma$の全ての部分割り当てを追跡したときのパスを考えます. ケース2での列挙により, 多くのパスが列挙されることになりますが, その中で割り当ての辞書順最小のパスを再び先頭から同じ方法で$\gamma$に基づいて辿ることで, $\gamma$で固定したが$\beta$で固定しなかった変数が全てわかり, $\beta$の情報を復元することができます.

3.5. 記述長

最後に, $\gamma,\mathsf{info}$の記述長を考えます. $\gamma$は$s-d$-制限なので, ありうる$\gamma$の総数は$|\mathcal{R}_{s-d}| = \binom{n}{s-d}\cdot 2^{n-s+d}$です. 次にありうる$\mathsf{info}$の総数を考えます. $\mathsf{info}$では「$i$番目の変数に$b_i$を代入する」という情報を$d$個含んでおり, $1\le i \le w$のため, ありうる$\mathsf{info}$の総数は高々$(2w)^d$となります.

一方で, $s$-制限の個数は全部で$\binom{n}{s}\cdot 2^{n-s}$個なので, 求める確率は

$$\begin{align*} \Pr_\alpha[\mathsf{DT}(f|_\alpha)>d] &\le \frac{(2w)^d\cdot \binom{n}{s-d}\cdot 2^{n-s+d}}{\binom{n}{s}\cdot 2^{n-s}} \\ &\le \left(\frac{4w s}{n-s} \right)^d \end{align*}$$

となり, 主張を得ます.

KLダイバージェンスの優モジュラ性と確率集中不等式

「エントロピーは劣モジュラ性をもつ」という事実は界隈の中ではとても有名で, エントロピーを最大化するということはある意味で多様性を大きくするということとみなせることから, この事実は劣モジュラ関数最大化の応用の一つとなりえます (この問題はNP困難ですが). 相互情報量の非負性とみなせるという説明がされることもありますが, 本記事ではこの事実をKLダイバージェンスの優モジュラ性の観点からと捉えます. この観点の利点として, Chernoff boundが導出できます. そもそも相互情報量はKLダイバージェンスの形で表すことができ, KLダイバージェンスは常に非負であることがJensenの不等式から簡単に示せるので, 突き詰めるとJensenにいきつきます. 凸って偉い.

注1. エントロピーはKLダイバージェンスの符号を逆にして定数を足した値なので, エントロピーの劣モジュラ性はKLダイバージェンスの優モジュラ性から直ちに従います. この意味でちょっとだけ一般化していると言えます.

注2. 実は優モジュラ性はChernoff boundの証明においては少しオーバーキルで, 実は優加法性から導出できます.

1. エントロピーと劣モジュラ性

---

定義1.1 (エントロピー).

有限集合$\Omega$上に値をとる確率変数$X$のエントロピー$\mathrm{H}(X)$とは
$$\begin{align*} \mathrm{H}(X) = \sum_{x\in \Omega}\Pr[X=x]\log\frac{1}{\Pr[X=x]} \end{align*}$$
によって定義される値である.

総和の各項$\log\frac{1}{\Pr[X=x]}$は事象“$X=x$"の情報量と呼ばれる値です. logの底は文脈によってまちまちですがここでは自然対数を考えることとします (底を2とするのがスタンダードですが, 文脈によっては自然対数を考えた方が便利なことがあります). 事象の確率が小さいほどその情報量は大きい値になっており, 直感的にはその事象が起きたときのびっくり具合を意味する値になっています. エントロピーとは情報量の期待値として定義されます.

定義1.2 (劣モジュラ性).

有限集合$V$に対し, 部分集合族上の関数 $f\colon 2^V \to \mathbb{R}$ が以下の条件を満たすとき劣モジュラ性をもつという:
$$\begin{align*} {}^{\forall}I,J \subseteq V,\,f(I\cup J)+f(I\cap J) \le f(I) + f(J). \end{align*}$$
上記の不等号を$\ge$に置き換えたときの性質を満たすとき, $f$は優モジュラ性をもつという.

言い換えれば, $-f$が劣モジュラ性をもつならば$f$は優モジュラ性をもつと定義します.

命題1.3 (エントロピーの劣モジュラ性).

自然数$n\in\mathbb{N}$に対し$\Omega^n$上に値をとる確率変数$X=(X_1,\dots,X_n)$を考え, 集合$I \subseteq [n]$に対し$X_I=(X_i)_{i\in I}$を$I$への射影とする. このとき, 関数$I \mapsto \mathrm{H}(X_I)$は劣モジュラ性をもつ.

2. KLダイバージェンスと優モジュラ性

---

有限集合$\Omega$上に値をとる二つの確率変数$X,Y$を考えそれぞれの周辺分布を$\mu_X,\mu_Y$とします. ここで, $\mu_X\colon \Omega\to [0,1]$は関数$\mu_X(x)=\Pr[X=x]$によって定まる関数です. 確率変数$X$の台 (support) を$\mathsf{supp}(X) =  \{x\in \Omega \colon \mu_X(x) > 0 \}$で定めます.

定義2.1 (KLダイバージェンス).

$\mathsf{supp}(X)\subseteq \mathsf{supp}(Y)$を満たす二つの確率変数$X,Y$のKLダイバージェンスとは以下で定義される量である:

$$\begin{align*} \mathrm{KL}(X||Y) &= \sum_{a \in \Omega} \Pr[X=a] \log\frac{\Pr[X=a]}{\Pr[Y=a]} \\ &= \mathbb{E}_{a \sim X}\left[ \log\frac{\mu_X(a)}{\mu_Y(a)} \right] \end{align*}$$
ただし, $0\log 0=0$として扱う.

(分子と分母がどっちかどっちか分からなくなるときがありますが, 私はfrac{}{}と同じ順番と覚えています)

KLダイバージェンスとはそれぞれの確率変数の分布から定まるので, $X$と$Y$が独立かどうかによって値が変化することはありません. エントロピーとKLダイバージェンスの間にはつぎの関係がなりたちます (簡単な計算から確認できます):

命題2.2 (エントロピーとKLダイバージェンス).

確率変数$U$を$\Omega$上の一様分布に従う確率分布とする. $\Omega$上に値をとる任意の確率変数$X$のエントロピー$\mathrm{H}(X)$は,
$$\begin{align*} \mathrm{H}(X) = \mathrm{H}(U) - \mathrm{KL}(X || U). \end{align*}$$

なお, 一様分布ならば$U=a$という事象は全て同じ情報量$\log|\Omega|$を持つので, $\mathrm{H}(U)=\log|\Omega|$です. 従って, エントロピーは一様分布からのKLダイバージェンスの符号を変えて並行移動したものと捉えることができます. ここで符号を変えたことで劣モジュラ性と優モジュラ性が入れ替わります.

命題2.3 (KLダイバージェンスの優モジュラ性).

二つのベクトル値確率変数$X=(X_1,\dots,X_n), Y=(Y_1,\dots,Y_n)$および$I\subseteq [n]$に対し, $\mathrm{KL}(I) \colon 2^{[n]} \to \mathbb{R}$を
$$\begin{align} \mathrm{KL}(I) = \mathrm{KL}(X_I || Y_I) \end{align}$$

と定める. 確率変数$Y_1,\dots,Y_n$が独立ならば, 関数$\mathrm{KL}(\cdot)$は優モジュラ性をもつ.

ここで, 確率変数$Y_1,\dots,Y_n$が独立であるとは, 任意の$y_1,\dots,y_n \in \Omega$に対して
$$\begin{align*} \Pr\left[ {}^\forall i\in[n],\,Y_i = y_i \right] = \prod_{i\in [n]}\Pr[Y_i=y_i] \end{align*}$$
が成り立つことを言います.

$\Omega^n$上の一様分布$U=(U_1,\dots,U_n)$を考えると$U_1,\dots,U_n$は独立かつそれぞれの$U_i$は$\Omega$上一様ランダムです. 従って$Y=U$としてKLダイバージェンスの優モジュラ性(命題2.3)を適用すると, $I \mapsto \mathrm{KL}(X_I || U_I)$は優モジュラ性をもちます. ところで, エントロピーとKLダイバージェンスの関係 (命題2.2) より
$$\begin{align*} \mathrm{H}(X_I) = \mathrm{H}(U_I) - \mathrm{KL}(X_I || U_I) \end{align*}$$
が成りたつため, $I \mapsto \mathrm{H}(X_I)$は劣モジュラ性を満たします (-1倍して並行移動しているだけなので). これは命題1.3を導出します.

ちなみに, 関数$\mathrm{KL}(I)$は単調性をもちます:
$$\begin{align*} {}^{\forall} I \subseteq J\subseteq[n],\, \mathrm{KL}(I) \le \mathrm{KL}(J). \end{align*}$$

この事実は射影関数$(x_j)_{j \in J} \mapsto (x_i)_{i\in I}$に対してKLダイバージェンスのデータ処理不等式を適用することで得られます.

3. KLダイバージェンスの優モジュラ性とChernoff bound

---

実はやることは以前の記事で紹介した, KLダイバージェンスに基づくChernoff boundの証明と全く同じです. 式変形の一部の不等式を優モジュラ性として解釈できることを説明します.

定理3.1 (Chernoff bound).

実数値をとる独立な確率変数$Y_1,\dots,Y_n$に対し, $\mu=\frac{1}{n}\sum_{i\in[n]}Y_i$とすると,
$$\begin{align} & \Pr\left[\frac{1}{n} \sum_{i\in[n]} Y_i \ge \mu + \varepsilon \right] \le \exp\left( - n \mathrm{KL}(\mu+\varepsilon||\mu)\right),\\ & \Pr\left[\frac{1}{n} \sum_{i\in[n]} Y_i \le \mu - \varepsilon \right] \le \exp\left( - n \mathrm{KL}(\mu-\varepsilon||\mu)\right). \end{align}$$

ただし, $p,q\in[0,1]$に対し$\mathrm{KL}(p||q)=\mathrm{KL}(\mathrm{Ber}(p)||\mathrm{Ber}(q)) = p\log\frac{p}{q} + (1-p)\log\frac{1-p}{1-q}$はBernoulli試行のKLダイバージェンスである.

二つの確率変数$X=(X_i)_{i\in[n]}, Y=(Y_i)_{i\in[n]}$に対し, (1)の定まる関数$\mathrm{KL}(I)$を考えます. $Y_1,\dots,Y_n$が独立ならばこの関数は優モジュラ性をもつ, すなわち

$$\begin{align*} {}^{\forall} I,J\subseteq [n],\,\mathrm{KL}(I\cup J) + \mathrm{KL}(I \cap J) \ge \mathrm{KL}(I) + \mathrm{KL}(J) \end{align*}$$
を満たします. 特に$I\cap J=\emptyset$のときは$\mathrm{KL}(I\cup J) \ge \mathrm{KL}(I) + \mathrm{KL}(J)$なので, 特に優加法性

$$\begin{align} \mathrm{KL}([n]) \ge \sum_{i \in [n]} \mathrm{KL}(i) \end{align}$$
を満たします (ここでは$\mathrm{KL}(\{i\})$を$\mathrm{KL}(i)$と略記しています).

定理3.1の証明に戻ります. ここでは(2)式のみを示しますが, (3)式も同様に示せます. 事象$\mathcal{E}$を$\mathcal{E}=\left\{\frac{1}{n}\sum_{i \in [n]} Y_i \geq \mu+\varepsilon\right\}$とし, $X=Y|_E$とします. つまり, $Y|_E$とは, $\mathcal{E}$を満たす$(y_1,\dots,y_n)\in\Omega^n$に対し

$$\begin{align*} \Pr[Y|_\mathcal{E} = (y_1,\dots,y_n)] = \Pr[Y=(y_1,\dots,y_n)|\mathcal{E}] = \frac{\Pr[Y=(y_1,\dots,y_n)]}{\Pr[\mathcal{E}]} \end{align*}$$
によって定まる確率変数です.

$X',Y'$を, 一様ランダムに選ばれた$i\sim[n]$に対し$X'=X_i$, $Y'=Y_i$と定義される確率変数とします. 簡単な計算から$\log\frac{1}{\Pr[E]}=\mathrm{KL}(X||Y)=\mathrm{KL}([n])$が示せます. 実際,
$$\begin{align*} \mathrm{KL}(X||Y) &= \mathbb{E}_{a \sim X} \left[ \log\frac{\Pr[X=a]}{\Pr[Y=a]} \right] \\ &= \mathbb{E}_a \left[ \log\frac{\Pr[Y=a|\mathcal{E}] }{\Pr[Y=a]}  \right] \\ &= \log\frac{1}{\Pr[\mathcal{E}]} \end{align*}$$

従って, (4)より
$$\begin{align*} \log\frac{1}{\Pr[E]} &= \mathrm{KL}(I) \\ &\geq \sum_{i \in [n]} \mathrm{KL}(i) \\ &= n\mathbb{E}_{i\sim[n]}\left[ \mathrm{KL}(Y_i||X_i)\right] \\ &\geq n D(Y'||X'). \end{align*}$$
ここで, 以前の記事の議論より$D(Y'||X')\geq \mathrm{KL}(\mu+t||\mu)$となり, (2)式を得ます.

4. むすびに

---

KLダイバージェンスの優モジュラ性からエントロピーの劣モジュラ性とChernoff boundが導出できることを解説しました. KLダイバージェンスの優モジュラ性は条件付きKLダイバージェンスを考えることによって証明できますが, 今回の記事では省いています.

KLダイバージェンスの一般化としてf-ダイバージェンスという概念が知られていますが, 命題2.3が成り立つようなf-ダイバージェンスを優モジュラf-ダイバージェンスと言い, これに基づいた集中不等式が証明されています (cf. [Masiha, Gohari, Yassaee, 2023]).

離散凸の文脈では劣モジュラ関数はある意味で凸な関数と見做されているため, この観点でいうとKLダイバージェンスは凹関数となります. 一方でKLダイバージェンス$\mathrm{KL}(\mu || \nu)$を二つの分布を受け取って実数値を返す関数とみなすと, $\mathrm{KL}\colon \Delta^2\to\mathbb{R}$ となります ($\Delta$は確率単体). このとき$\mathrm{KL}(\cdot)$は凸関数となります. KLの凸性はものすごく重要です.

付録. 優モジュラ性の証明

---

ここではKLダイバージェンスの優モジュラ性 (命題2.3) を証明します. 準備として条件付きKLダイバージェンスの概念を導入します.

定義A.1 (条件付きKLダイバージェンス)

二つの確率変数のペア$(X_1,X_2), (Y_1,Y_2)$に対し, 条件付きKLダイバージェンスを以下で定義する:
$$\begin{align*} \mathrm{KL}(X_1|X_2||Y_1||Y_2) = \mathbb{E}_{x\sim X_2}\left[ \mathrm{KL}(X_1|_{X_2=x} || Y_1|_{Y_2=x}) \right]. \end{align*}$$

条件付きKLダイバージェンスの重要な二つの性質を導入します.

補題A.2 (Chain rule).

$$\begin{align*} \mathrm{KL}((X_1,X_2) || (Y_1,Y_2)) = \mathrm{KL}(X_2||Y_2) + \mathrm{KL}(X_1|X_2 || Y_1|Y_2) \end{align*}$$

証明.

気合いで計算して証明します. $\mu,\nu$をそれぞれ$(X_1,X_2)$, $(Y_1,Y_2)$の分布とし, $\mu_i,\nu_i$をそれぞれ$X_i,Y_i$の周辺分布とします. このとき

$$\begin{align*} &\mathrm{KL}((X_1,X_2)||(Y_1,Y_2)) - \mathrm{KL}(X_2||Y_2) \\ &= \mathbb{E}_{(a,b)\sim\mu}\left[\log\frac{\mu(a,b)}{\nu(a,b)}\right] - \mathbb{E}_{b\sim\mu_2}\left[\log\frac{\mu_2(b)}{\nu_2(b)}\right] \\ &= \mathbb{E}_{(a,b)\sim\mu}\left[\log\frac{\mu(a,b)}{\nu(a,b)}\right] - \mathbb{E}_{(a,b)\sim\mu}\left[\log\frac{\mu_2(b)}{\nu_2(b)}\right] \\ &= \mathbb{E}_{(a,b)\sim \mu}\left[ \log\frac{\mu(a,b)/\mu_2(b)}{\nu(a,b)/\nu_2(b)}\right] \\ &= \mathbb{E}_{(a,b)\sim \mu} \left[\log\frac{\Pr[X_1=a|X_2=b]}{\Pr[Y_1=a|Y_2=b]}\right] \\ &=\mathbb{E}_{b\sim X_2}\left[\mathbb{E}_{a\sim X_1}\left[ \log\frac{\Pr[X_1=a|X_2=b]}{\Pr[Y_1=a|Y_2=b]} \middle| X_2=b\right]\right] \\ &= \mathrm{KL}(X_1|X_2||Y_1||Y_2). \end{align*}$$

(証明終).

補題A.3 (conditioning increases KL).

二つの確率変数$Y_1$と$Y_2$が独立ならば

$$\begin{align*} \mathrm{KL}(X_1|X_2||Y_1|Y_2)\geq \mathrm{KL}(X_1||Y_1). \end{align*}$$

証明.

KLダイバージェンスを関数$\mathrm{KL}\colon \Delta^2\to \mathbb{R}$とみなしたとき, 凸性を持つことから, Jensenの不等式より

$$\begin{align*} \mathrm{KL}(X_1|X_2||Y_1|Y_2)&=\mathbb{E}_{x\sim X_2}[\mathrm{KL}(X_1|_{X_2=x}||Y_1|_{Y_2=x})] \\ &\geq \mathrm{KL}(\mathbb{E}_x[X_1|X_2=x]||\mathbb{E}_x[Y_1|Y_2=x]) & & \text{(Jensen)}\\ &=\mathrm{KL}(X_1||Y_1) \end{align*}$$

なお, 最後の等号において$Y_1$と$Y_2$の独立性を使っています.

(証明終)

実は, 二つの確率変数$X_1,X_2$の相互情報量を$I(X_1;X_2)$とすると, $\mathrm{KL}(X_1|X_2||Y_1|Y_2) - \mathrm{KL}(X_1||Y_1) = I(X_1;X_2)$が成り立ちます (計算で確認できます). 相互情報量$I(X_1;X_2)$とは,
$$\begin{align*} I(X_1;X_2) = \mathrm{KL}(\mu||\mu_1 \otimes \mu_2) \end{align*}$$
で定義される値です. つまり$(X_1,X_2)$がどれだけ直積分布から離れているかを測る量であり, $\mathrm{KL}$の非負性から常に非負です.

以上で優モジュラ性の証明の準備がおわりました.

命題2.3の証明.

任意の$I,J\subseteq[n]$に対し, chain rule (補題A.2) より

$$\begin{align} \mathrm{KL}(I\cup J) - \mathrm{KL}(I) = \mathrm{KL}(X_{I\cup J}|X_I || Y_{I\cup J}|Y_I) = \mathrm{KL}(X_{J\setminus I}|X_I || Y_{J\setminus I}|Y_I) \end{align}$$

最後の等号では, $X_I$が与えられたとき, $X_{I\cup J}$のランダムネスは$X_{J\setminus I}$にあることを用いています. 同様に

$$\begin{align} \mathrm{KL}(J)-\mathrm{KL}(I\cap J) = \mathrm{KL}(X_J|X_{I\cap J}||Y_J|Y_{I\cap J})=\mathrm{KL}(X_{J\setminus I}|X_{I\cap J}||Y_{J\setminus I}|Y_{I\cap J}). \end{align}$$
補題A.3より, $(5)\ge (6)$となるので主張を得ます.

埋め込みクリーク問題

与えられたグラフ$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*}$$
を得ます.

STOC2日目以降の感想 (主にsunflower conjecture周り)

STOCが終わったので記憶が残っているうちに勢いに任せて前回に引き続きSTOC参加記(2日目〜5日目)を駆け足で書いていきます. 聴講して特に印象に残ったものについて記載しています. 勢いに任せて書いているのでテクニカルな内容はありません. ただし, sunflower lemmaの話については結構面白いと思ったので自分が理解した範囲で定義とかを書いていきます.

2日目

朝にLength-Constrained Expandersというワークショップに参加しました. 近年巷を騒がせているエクスパンダー分解や小直径分解という概念があるのですが, length-constrained expanderとはどちらの性質も同時に兼ね備えた分解を与える概念のようです. どちらの分解でも共通して頂点部分集合の分割$\mathcal{P}=(P_1,\dots,P_\ell)$であって, 各部分集合$P_i$のなる誘導部分グラフ$G[P_i]$が小直径または(Cheeger定数の意味で)エクスパンダーグラフとなるようなものを求めます. そして各$P_i$を縮約して得られるグラフに対して再帰的に分解を適用することによって, エクスパンダーからなる階層構造が得られます.

端的に言えば, 最悪時の問題例を分解によってエクスパンダー上で解くことに帰着するみたいなことをするようです. length-constrained expanderとは小直径分解とエクスパンダー分解両方の嬉しい性質を同時に達成するような分解らしいです.

2日目の午後は自分の発表を行いました. その次のセッションはランダムウォークなど確率解析のセッションでした. 時差ボケであまりちゃんと聞けなかったのですが最後の発表

On the Fourier Coefficients of High-Dimensional Random Geometric Graphs (Kiril Bangachev and Guy Bresler)

が印象的でした. この論文ではランダム幾何グラフとErdős--Rényiグラフの識別問題に対してよく知られる計算量と情報理論のギャップ (computational-statistical gap) について議論しており, low-degree polynomialと呼ばれるアルゴリズムのクラスでは両者のギャップが埋まる, という話でした.

3日目

午後は誤り訂正符号のセッションに行きました. 近年のTCSでは3クエリのlocally correctable codeのレートに関する効率性の下界を, これまで知られていたものより指数的に改善したという論文

An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes (Pravesh K. Kothari, Peter Manohar)

の発表がありました. これはTCSの符号界隈で非常に大きな話題になりました.

その次のセッションは

Complexity-Theoretic Implications of Multicalibration, (Sílvia Casacuberta, Cynthia Dwork, Salil Vadhan)

でした. この論文はarXivに出た瞬間から個人的に注目していた論文です. additive combinatoricsにおけるdense model theorem (Green-Taoの定理の証明で重要な役割を果たした定理), Impagliazzoのhardcore補題, そしてFrieze-Kannanの正則化補題がどれも同じような構成的証明を与えていることに着目して共通の一般化を与えたという論文があるのですが, この論文はそれをmulticalibrationの観点でさらに一般化したというものです. この論文もquanta magazineの記事で紹介されています.

4日目

Applications of Turán-type problems in Theoretical Computer Scienceというワークショップに参加しました. Turánの定理とは完全グラフ$K_r$を部分グラフとして含まないグラフのうち最も辺数が多いものは, 等分割された完全$(r-1)$部グラフであるという主張です. 例えば三角形を含まないグラフの中で最もデンスなのは完全二部グラフです.

この問題は次のような自然な設定で登場します:

$n$個の電池があり, そのうち$r$個のみが充電されていて他は全て充電が空なのですが, どれが充電されていてどれが空か分からないとします. 手元には懐中電灯があり, 充電されている電池を2個入れると光ります. $n$個の中から二つの電池を入れて試すという試行を何回か行って懐中電灯を光らせたいとき, 最も試行回数を少なくするにはどうすればよいか?

グラフの言葉に翻訳すると以下になります: $n$個の頂点があってサイズ$r$の独立点集合を含まないグラフのうち最も辺数が少ないものは何か? グラフを一つ固定したとき, 各辺は懐中電灯の一回の試行に対応します. このグラフがもしもサイズ$r$の独立点集合$I$を持つならば, この頂点部分集合$I$が「充電された電池」であったときにこの試行で懐中電灯を光らせることができません. この解となるグラフの補グラフをとるとTuránの定理の設定になります.

Turán-typeな問題とは, 固定されたグラフ$H$を含まないグラフの中で最も密なものは何かという極値グラフ理論の問題です. 例えば奇数長の閉路は完全二部グラフを考えれば辺数$\Omega(n^2)$を達成しますが, 四角形を含まない任意の$n$頂点グラフは辺数が$O(n^{1.5})$になります (こちらの記事で証明しています). 応用として, ワークショップではErdősの内周予想やそれの最近の進展について取り上げられていました. 特に興味深かったのは$H=C_8$のときは未解決であるということでした. つまり, 長さ$8$の閉路を含まない$n$頂点グラフのうち最大辺数を$\mathrm{ex}(n;C_8)$とすると現在知られている最善のバウンドが

$$\Omega(n^{6/5}) \le \mathrm{ex}(n;C_8) \le O(n^{5/4})$$
となっており, このギャップを埋めるのはこの分野の中心的な未解決問題らしいです.

5日目

前日に引き続きTuranのワークショップに参加しました. とあるpseudorandomnessを満たす部分集合族を使ってsunflower lemmaの改善を与えた論文の話がありました. 集合$S_1,\dots,S_r \subseteq [n]$は, 全ての$i\neq j$に対して$S_i \cap S_j = S_1 \cap \dots \cap S_r$を満たすとき, $r$-ひまわりと呼びます. 

$[n]$上の集合族$\mathcal{S}=\{S_1,\dots,S_m\}$は, ある$S_{i_1},\dots,S_{i_r}\in\mathcal{S}$が$r$-ひまわりをなすとき, $r$-ひまわりを含むといいます. $r$-ひまわりを含まない部分集合族$\mathcal{S}$であって最も多くの集合を持つものはどのようなものになるでしょうか?

定理 (Erdős-Rado, '60)

集合族$\mathcal{S}=\{S_1,\dots,S_m\}$が$|S_i|\le w$を満たすとする. もし$|\mathcal{S}| > w! \cdot (r-1)^w$を満たすならば, $\mathcal{S}$は必ず$r$-ひまわりを含む.

この$m$のバウンド$w!\cdot (r-1)^w$を漸近的に改善できるのではないか? というのがひまわり予想です.

予想 (Erdős-Rado, '60).

集合族$\mathcal{S}=\{S_1,\dots,S_m\}$が$|S_i|\le w$を満たすとする. 各$r \ge 3$に対してある定数$C>0$が存在して, $|\mathcal{S}|>C^w$を満たすならば, 集合族$\mathcal{S}$は必ず$r$-ひまわりを含む.

Alweiss, Lovett, Wu, and Zhang (STOC20) はErdős-Radoの定理のバウンドを改善し以下の定理を証明しました:

定理 (Alweiss, et al. (2021)).

集合族$\mathcal{S}=\{S_1,\dots,S_m\}$が$|S_i|\le w$を満たすとする.  各$r \ge 3$に対してある定数$C>0$が存在して, $|\mathcal{S}|>(Cr^3 \log w \log\log w)^w$を満たすならば, 集合族$\mathcal{S}$は必ず$r$-ひまわりを含む.

ワークショップではこの定理の証明の雰囲気が紹介されました. まず, 集合族$\mathcal{S}$の擬似ランダム性を以下で定義します:

定義.

$[n]$上の部分集合族$\mathcal{S}=\{S_1,\dots,S_m\}$が$|S_i|\le w$を満たすとする. この集合族$\mathcal{S}$は, 任意の$T\subseteq[n]$に対して
$$\begin{align*} \Pr_{S \sim \mathcal{S}} [ S \supseteq T ] \le \kappa^{|T|} \end{align*}$$
を満たすとき, $\kappa$-spreadという.

部分集合族$\mathcal{S}=\{S_1,\dots,S_m\}$および$T\subseteq[n]$に対し, $T$のリンク$\mathcal{S}_T$とは, 部分集合族であって,
$$\begin{align*} \mathcal{S}_T = \{S\setminus T \colon T \subseteq S\in\mathcal{S} \} \end{align*}$$
によって定まるものです. リンクの言葉を使うと, $\mathcal{S}$が$\kappa$-spreadであるというのは, 任意の$T$のリンク$\mathcal{S}_T$が
$$\begin{align*} |\mathcal{S}_T| \ge \kappa^{-|T|}\cdot |\mathcal{S}| \end{align*}$$
を満たすことを意味します ($\mathcal{S}_T$の要素数は$T$を含む$\mathcal{S}$に属す部分集合の個数に等しいから).

重要な観察として, もしもリンク$\mathcal{S}_T$が$r$-ひまわり$\{S'_1,\dots,S'_r\}$を含むとしましょう. すると, $S'_1\cup T, \dots, S'_r \cup T$は$\mathcal{S}$における$r$-ひまわりになっているはずです. すなわち, リンクをとった後にひまわりがあるならば元の集合族に復元することができます.

適切な$\kappa$を選びます. もしも今持っている集合族$\mathcal{S}$が$\kappa$-spreadでないとするならば, 定義よりある$T$が存在して$|\mathcal{S}_T| > \kappa^{|T|}\cdot |\mathcal{S}|$となります. このリンク$\mathcal{S}_T$に対してひまわりの存在性を言えば, $\mathcal{S}$がひまわりを持つことが示せます. これを再帰的に繰り返していくと, $\kappa$-spreadingな集合族に対して議論すれば良いことになります. Alweissらの貢献は$\kappa$-spreadingな集合族に対してはdisjointな部分集合$S_{i_1},\dots,S_{i_r}$がとってこれることを示したこと(らしい)です. disjointな部分集合族はひまわりをなすので, これで定理の主張が証明できたことになります.

STOC1日目の感想 (LLMの話とbest paper sessionのまとめ)

せっかくSTOCに参加しているので日記を書こうと思いたち, 勢いに任せて筆を進めています. 2日目以降は筆が乗らないかもしれません.

今回のSTOCは最初のワークショップではLLMなどのAI分野においてアルゴリズムの理論研究がどのように貢献できるのかという話をしていました. 以下に続く文章はそのWSを聞いて私が解釈したものですので, 内容の正確性は保証しません. あくまでも私が解釈したものなので, AIに関して何かを述べる際はこの記事を情報源にはしないでください.

例えば文章が途中まで与えられた「次の単語は何か？」を学習する際, まず単語ごとに区切りそれぞれの単語を高次元ベクトルに埋め込み (多分Word2Vecみたいな話), 次に出てくる単語の条件付き分布を推定するということをします. この条件付き分布は何らかの分布に従うと仮定しており, 通常はある高次元のパラメータ$\theta$を持ちます (例えば正規分布は平均と分散で二つのパラメータをもつ). 深層学習とはこの「何らかの分布」のテンプレートの一例にすぎず, そのテンプレの中で尤度関数を最適化するという作業に他なりません. 具体的には線形作用と成分毎の非線形作用を交互に組み合わせる分布を考えており, この線形作用の重みがパラメータに対応します. chatGPTとかをみるとあたかも魔法のようなことをしているように見えますが, 実際は次の単語の条件付き分布がある特定のテンプレに従うと仮定し, 与えられたデータセットに最も近いテンプレを見つけるにすぎません.

教師あり学習だと点とそのラベルの組があらかじめデータセットとして与えられ, 未知の点が当てられたときにその点のラベルは何かを推測するということを考えます. この問題点は高精度な推測をするためには多くのデータセットが必要になるという点です. しかしながら, 膨大な点とそれに対応するラベルの組を得るという作業は大変です.

ところが「次の単語は何か?」という問題の場合はインターネット上のデータ (wikiの記事など) から文を持ってくれば膨大なデータセットを容易に得ることができるので, 前段落の問題点は解消されます. あとはこの膨大なデータセットを用いていかに効率よく最適なパラメータを得るかというアルゴリズムのタスクが勝負になります. ここではスーパーコンピュータなどを用いて大規模な並列計算を行うことも視野に入れて「並列化しやすい」アルゴリズムを設計するみたいなことも視野に入れます.

ワークショップではdiffusion modelについての話も出ました. なんとなく「diffusion model」と聞くとたいそうに聞こえますが端的に言えば空間上のただのランダムウォークだと私は思っています. 例えば「子犬と遊ぶ子供」という文からそれに対応する画像を生成するタスクを考えてみましょう. このとき, 任意の画像全体の空間$\mathbb{R}^N$を考え, その上で点$x \in \mathbb{R}^N$に対し小さなランダムなノイズを加えるという操作を繰り返しましょう. $t$回繰り返して得られるベクトルを$x_t$とすると, 十分大きな$t$に対して$x_t$は標準正規分布$N(0,I)$に近いです. diffusion modelとはノイズを除去する過程のモデルであり, $x_t$が与えられたときの$x_{t-1}$の条件付き確率が平均$\mu_t(x_t,t)$, 分散$\sigma_t(x_t,t)$の正規分布に従うと仮定してこのパラメータを最適化するという作業に他なりません. このようにすることで「子犬と遊ぶ子供」という文から実際にそれを表現する画像をサンプリングすることができます. データセットは「子犬と遊ぶ子供」の画像からなります. このデータセットはまずネットサーフィングして画像と脚注の組を得ます. 次に脚注の文章を高次元に埋め込みます. この埋め込みは意味が似てる二つの文章は埋め込んだ後も何らかの意味で距離が近いものになっているとします. すると「子犬と遊ぶ子供」に対応する点に近い点に対応する脚注を持つ画像を抽出することで大量のデータセットを用意することができます (この辺は少し私の理解が曖昧なので不正確かもしれません).

ワークショップの二人目の発表はAtri Rudraでした. 彼はEssential Coding Theoryの著者の一人なので私の中では誤り訂正符号をやってる人というイメージだったので, このような分野で研究をされているというのは意外でした. 今日「Transformer」と呼ばれる技術を算術回路に落とし込み, 効率的な算術回路を提案することでより学習を効率的に行うという旨の話でした.

Transformerでは, まず与えられた文章を$N$個の単語に分解し, それぞれの単語を$d$次元ベクトルに埋め込みます. こうして得られた$N$個のベクトルを並べて得られる行列を$X \in \mathbb{R}^{N \times d}$ とします. 深層学習では各レイヤーで, $X$を$Nd$次元のベクトルとみなして$X_t \leftarrow \sigma (W_t X_{t-1})$という更新式に基づいて$X_T$を出力するときの行列$W_t$を最適化で求めるわけですが, TransformerのAttentionと呼ばれるプロセスでは
$$X_t \leftarrow \sigma (Q_tX_{t-1}X_{t-1}^{\top} K_t)$$
という更新式 (ここで$Q_t,K_t$は行列) を繰り返します (これが何でうまくいくかは分かりません). この$Q_t$と$K_t$がパラメータになっており, 学習ではこのパラメータを最適化します. あまりちゃんとわかっていませんがここでの行列がある種の対称性を持っていれば効率的に更新できるみたいな感じの話だと思います. ただしここでは行列への要請として対称性だけではなく, (勾配法の適用を念頭に)パラメータでの微分可能性も要請されていました (行列かけるだけだったら常に微分可能なんじゃないの？と思ったけどよくわからなかった). この辺の話では面白いことにSETH-hardnessの論文があったりするようです.

LLMのワークショップの後はbest paper sessionがありました. 今回のSTOCは3件のbest paperがあり, それぞれ

• Single-Source Shortest Paths with Negative Real Weights in $\tilde{O}(mn^{8/9})$ Time, Jeremy Fineman.
• Near Optimal Alphabet-Soundness Tradeoff PCPs, Dor Minzer and Kai Zhe Zheng.
• Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis, Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu.

でした.

一つ目の論文は負辺持ちグラフ上の単一始点最短経路問題に対してBellman-Fordより速いアルゴリズムを提案するというものです. この問題は2022年のFOCSの論文で$\tilde{O}(m\cdot \mathrm{poly}\log W)$時間で解くアルゴリズム ($W$は最大絶対値重み) が提案されていましたが, このアルゴリズムは反復回数が$\mathrm{poly}\log W$に依存するためいわゆる「弱多項式」時間アルゴリズムです. 一方でこちらの論文は一反復の計算に$\tilde{O}(m n^{2/9})$時間かかる操作を$O(n^{2/3})$回繰り返すというものであり, いわゆる「強多項式」時間アルゴリズムです.

二つ目の論文はPCP定理のアルファベットサイズとsoundnessのトレードオフに関する論文です. PCP定理についてはこちらの記事で説明をしていますが, 「SATは確率的検証可能できる」ことを主張する定理です. SAT (より一般にクラスNPの問題) は, 入力がYesインスタンスのときにYesたりうる証拠たりうる文字列 (例えばSATなら充足割り当て) が存在しそれをみたときは受理し, Noインスタンスのときはどんな文字列が与えられても拒否する検証者(verifier)が存在します. 確率的検証とは証拠として与えられた文字列のうちランダムに選んだ$q=O(1)$個だけをみて受理/拒否を判定する検証を指します. 検証者の受理確率について, 入力がYesインスタンスならば確率$\approx 1$で受理し, Noインスタンスに対しては確率$\le \delta$で受理するものを考えます. ここのパラメータ$\delta$をsoundnessといいます. soundnessパラメータ$\delta$は小さければ小さいほどよいです.

PCPはそのアルファベットサイズ$|\Sigma|$を大きくすることによってクエリ数$q$を保ったままsoundnessを小さくしていく (Razのpararrel repetition) ことができますが, $|\Sigma|$と$\delta$の間のほぼ最適なトレードオフを見つけたというのが今回の論文の主張のようです.

三つ目の論文もPCP定理の改善の話で, パラメタ化計算量の文脈におけるPCP定理の話でした. PCP定理ではNPのwitnessを「符号化」して確率的検証できる証明に変換するのですが, この「符号化」で追加する冗長性をいかに短くできるかという文脈を考えます. パラメタ化計算量の文脈では考える入力のクラスを制限してより効率的なアルゴリズムを得るという研究をしますが, 一方でその困難性についてもいろいろわかってきており, 「NP困難性」に対応する概念として「W[1]困難性」という概念があります. 一般にW[1]困難な問題はFPT時間では解けないだろうと予想されており, 代表的な問題として$k$-クリーク問題があります. そしてW[1]困難な問題に対しても近似アルゴリズムを設計したり何らかの仮定の下での近似不可能性を示す研究もあります. この近似不可能性の文脈でよく出てくるのが PIH (parameterized inapproximatability hypothesis) という予想です. これはMAXSATのギャップ問題のようなパラメタ化問題がFPT時間で解けないという予想です. 今回の論文は指数時間仮説(ETH)の下でPIHが成り立つことを示しており, パラメタ化計算量における「PCP定理」を証明したという論文のようです. 普通のPCP定理の証明を考えるとNP証明を「符号化」するということを考えますが, この符号化によって対応するCSPのインスタンスのパラメタがめちゃくちゃになってしまうのが難しいポイントだと私は解釈しています. 代わりにW[1]困難な問題 vector CSPというものを考えるようです. 一般にNP証明からPCPに符号化する際のオーバーヘッドが定数倍で済むならば$\mathsf{ETH} \Rightarrow \mathsf{Gap}\text{-}\mathsf{ETH}\Rightarrow \mathsf{PIH}$が成り立つと思うのですが, このholy grailにはまだまだ遠いようです.

こうしてみるとbest paperのうち2/3はPCP定理なので今回はSymposium on Theory of pCp theorem (STOC) なのかもしれません.

best paper sessionの後はTCS4Allのイベントがありました. 本来ならばLuca Trevisanが話をする予定だったのですが残念なことに先週亡くなってしまったため, Pravesh KothariがLucaの作成したスライドに基づいてスペクトルグラフ理論の話をしていました. ほとんど知っている内容だったのですが改めて聞くとやはりLucaの偉大さが感じられる非常に素晴らしい内容でした.

coffee breakや懇親会ではいろんな人と話をしましたが, Yuhao Liとの雑談でTFNPにおけるPCP定理の話が興味深かったです (重要な未解決問題らしい). また, 私は加法的組合せ論に基づく平均時から最悪時への帰着が好きなので, その研究グループの一人のIgor Shinkarと話ができたのがとても良かったです. 大阪さんから聞いた遷移問題のPCPの話も面白かったです.

Luca Trevisanについて

Luca Trevisanが癌で52歳の若さで亡くなったという衝撃的なニュースが飛び込んできました.

Via Salil Vadhan: Luca Trevisan, a great complexity theorist, lost his battle with cancer today at the age of 52.

— Lance Fortnow (@fortnow) June 19, 2024

直接の面識は全くないのですが, 彼の多くの論文や結果, それにまつわる深い洞察は私の数学に重要な影響を与えており, 来週のSTOCでのワークショップでの彼の講演を直接見れるのをものすごく楽しみにしていただけに非常に残念に思います. STOCのワークショップでのスライドは準備されていたとのことですので, まさに「生涯現役」の研究者であるといえるでしょう. 理論計算機科学は世界的に非常に重要なリーダーの一人を喪失してしまいました.

彼の有名なブログ in theory は計算量理論, 加法的組合せ論, エクスパンダーグラフなど幅広い理論の最近の動向や手法を概説してくれるとても素晴らしいものであり, Terrence TaoのWhat's new や Boaz Barak の Windows On Theory などと並んで私のブログのスタイルに大きな影響を与えた存在でです.

計算量理論では, 例えばこちらのページのランダム抽出器の節で紹介した[Trevisan, 2001]や, こちらのページで紹介しているHardness vs. Randomnessに対して誤り訂正符号のlocal list-decodingに基づくアプローチを提案した[Sudan, Trevisan, Vadhan, 2001]が非常に有名です (もちろん, これに限らずもっと色々ありますが). また, Bogdanovと一緒に平均時計算量の非常に有名な教科書も執筆しています.

他にもスペクトルグラフ理論の文脈でよく知られるhigher-order Cheeger inequality (普通のCheeger不等式はグラフの頂点集合を二分割したときのカット辺の本数に関する不等式だが, higher-orderではグラフを$k$分割したときのカット辺の本数に着目する) の論文[Lee, Gharan, Trevisan, 2014]も有名です. この話はTrevisanによる解説記事があります.

また, 加法的組合せ論とその理論計算機科学への応用にまつわる様々な解説記事や講義ノート

• Guest column: additive combinatorics and theoretical computer science
• A mini course on additive combinatorics

も出しており, 私はこれらから加法的組合せ論の多くを学びました.

最近ではBecchettiらの研究グループでグラフ上の合意ダイナミクスと呼ばれるマルコフ連鎖やそれに基づくコミュニティ検出についての研究も精力的に行っており, 私の研究分野に非常に近い論文

• The Minority Dynamics and the Power of Synchronicity, Becchetti, Clementi, Pasquale, Trevisan, Vacus, Ziccardi, SODA24
• Stabilizing consensus with many opinions, Becchetti, Clementi,  Natale, Pasquale , Trevisan, SODA16
• Simple dynamics for plurality consensus, Becchetti , Clementi , Natale, Pasquale, Silvestri , Trevisan, SPAA14
• Find Your Place: Simple Distributed Algorithms for Community Detection, Becchetti, Clementi, Natale, Pasquale, Trevisan, SICOMP, 2020 (会議版はSODA2017)
• Average Whenever You Meet: Opportunistic Protocols for Community Detection, Becchetti, Clementi, Manurangsi, Natale, Pasquale, Raghavendra, Trevisan, ESA2018.

を出しており, その多くがSODAなどのトップ会議に採択されています.

私はTrevisanと直接交流したことはないのですが, 理論計算機科学の幅広い文脈でいつも見てよく資料で勉強させていただいた先生が若くして亡くなられたという事実に深い悲しみを覚え哀悼の意を捧げたいと思います.

高次元エクスパンダーの集中講義をしました

東北大数学科で高次元エクスパンダーに関する集中講義を行いました。講義資料は私のページから誰でも無料で見れるようになっています。集中講義ではランダムウォークを定義し、エクスパンダーグラフを定義しAlon-Boppanaの定理の証明概要を与えてラマヌジャングラフの話だけをして、単体複体の定義とそのエクスパンダー性を定義して、最後にマトロイドを定義し基交換ウォークの混交性を証明しました。高次元エクスパンダーに関する日本語のちゃんとした解説資料は自分の知る限り全くといって良いほどないので、この概念を日本に輸入する上で非常に大きな意義のある講義/講義資料になっていると自負しています。嬉しいことに資料も非常に多くの人に好評をいただけました。

そもそも集中講義を受講したことがなくどのようなものかすら全く知らなかったのですが、私が行った集中講義ではまず最初に談話会と呼ばれる1時間程度の講演を行い、その翌日から4日間、15時から19時くらいまで黒板を使って定理の証明とかキモチを語るというものでした。実際やってみるまでどのような雰囲気かわからなかったのでとりあえず全力で講義資料を準備したおかげで講義そのものは全体的にスムーズに進み、マトロイドの基交換ウォークの混交性の証明までちゃんと話せたのは非常に良かったです。ちなみに談話会では自己紹介的な側面もあるらしく、どんな内容でも良いもののある程度自分の研究トピックに絡んだものであるのが良さそうです。聴衆はピュアマスの人が多いでしょうから、やはりピュアマスのTCSにおける応用の話をするとものすごく食いつきが良かったです。

ピュアマスの方々は黒板での議論を好むというイメージは昔からなんとなくあったものの、予想以上でした。最適化理論のサマースクールという位置付けで毎年夏に行われる組合せ最適化セミナーでは3日間、各日にそれぞれ1名の講演者が計3時間の講義をスライドを用いて行うというものがあるのですが、私の集中講義は毎日4時間を4日間の計16時間あったわけですので時間の単純計算で組合せ最適化セミナーの講師を5回務めたことになったわけです（講義資料の準備も考えるともっとありそう）。

一方でスライドでの発表と違って聴衆の咀嚼のスピードに合わせてこちらの講義のスピードも調節できるというのが黒板発表の大きなメリットであるように感じました。もちろん、これは聴衆が忍耐強く頑張って咀嚼してくれるというのが前提の話になりますが。

聴衆はそれなりに多くの方に来ていただけました。何人かの学生にも積極的に核心をついた質問やご指摘をいただき、自分の講義資料のどの部分が良くないかなどを見直す良いきっかけになりました。

数学科で集中講義をするという機会はなかなかないかもしれませんが、やはり応用を見据えていくにつれこのような機会は将来的に他の方も経験するようなことがあるかもしれません。（当たり前なことも含まれていますが）板書で講義をする機会のある人のためにいくつか助言を残しておくと

• 講義資料はちゃんと作った方がよい（特に、各日にどこからどこまで話すかは事前に決めるべき）
• 私の資料の各章はある程度具体例をスキップしても話すと1日4時間くらいかかります。これが目安になると思います
• やはり細かい証明を与える前にまずその概要とか道筋を話すと聴衆の食いつきが良い
• 一方で直感的な説明や式変形だけを資料に書いてしまうと、厳密に式を追いたい人は満足しないので、資料には書いておいた方が良い
• 既存結果は誰がいつ発表したものかはちゃんと把握しておいた方が良い (誰が証明したのか？と聞かれることもある）
• 基本的に白と黄色で説明するのが多分良い (教室依存だけど赤とかだと場所によっては見づらくなりうる）

などでしょうか。おかげさまで講義終了後に飲んだビールと食べた牛タンはめちゃくちゃ美味しかったです。ありがとうございました。

凸共役と集中不等式

 凸解析のツールの一つとして凸共役という概念があります. $I\subseteq \mathbb{R}$上で定義された実関数$f$の凸共役とは
$$f^*(a) = \sup_{x\in I}\{ax - f(x)\}$$
で定義されます. 通常は$I=\mathbb{R}$や$I=(0,\infty)$を考えます. ここでは凸解析の理論には踏み込まず, この概念が確率集中不等式の文脈でどのように登場するかを説明します.

確率集中不等式とは, 実確率変数$X$がある点 (通常は期待値$\mathbb{E} X$) から離れる確率がどれくらい小さくなるかを評価する不等式です. (本記事では基本的に確率変数は全て期待値や分散が存在するものを考えます). 次の不等式を使います:

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

$X$を非負確率変数と任意の正の数$z>0$に対し, $\Pr[X \ge z] \le \frac{\mathbb{E}X}{z}$.

本記事の目標は$\Pr[X \ge \mathbb{E} X  + a]$を上から抑えることです. 簡単な式変形により, 任意の$\lambda>0$に対し
$$\begin{align*} \Pr[X \ge \mathbb{E} X + a] &= \Pr\left[ \mathrm{e}^{\lambda (X - \mathbb{E} X)} \ge \mathrm{e}^{\lambda a}\right] \\ &\le \mathrm{e}^{-\lambda a} \cdot \mathbb{E} \mathrm{e}^{\lambda ( X - \mathbb{E} X)  } \end{align*}$$
を得ます (一つ目の不等式では$\lambda>0$を利用し, 二つ目の不等式でマルコフの不等式を用いた). ここで, $\lambda>0$に対し$\psi_X(\lambda):=\log\mathbb{E}\mathrm{e}^{\lambda (X - \mathbb{E} X)}$とおくと,
$$\begin{align*} \log \Pr[X \ge \mathbb{E} X + a ] \le - (\lambda a - \psi_X(\lambda)). \end{align*}$$
この不等号は任意の$\lambda > 0$で成り立つので, 最適な$\lambda>0$を選ぶと
$$\begin{align*} \log \Pr[X \ge \mathbb{E} X + a ] \le - \sup_{\lambda > 0}\{\lambda a - \psi_X(\lambda)\} \end{align*}$$
となり, 右辺はまさに凸共役 $\psi_X^*(a)$になっています. 従って以下を得ます:

命題2.

確率変数$X$に対し, そのlogMGFを$\psi_X$とする. このとき, $\Pr[X\ge \mathbb{E} X + a] \le \mathrm{e}^{ - \psi_X^*(a)}$.

以上より, 凸共役$\psi_X^*(a)$の下界が得られればそこから集中不等式を導出できます. なお, $\lambda \le 0$に対しても$\psi_X(\lambda)$を定義することは可能でそこからlower tailを得ることができます. また, $\psi_X$は凸関数であることが知られており (ヘルダーの不等式を用いると示せる), 凸共役の性質より凸共役を2回とると元に戻ります.

独立な確率変数$X_1,\dots,X_n$に対して$X=X_1+\dots+X_n$と表せたとします. このとき
$$\mathbb{E}\mathrm{e}^{\lambda X} = \prod_{i=1}^n \mathbb{E}\mathrm{e}^{\lambda X_i}$$
となることから$\psi_X(\lambda) = \sum_{i=1}^n \psi_{X_i}(\lambda)$を得ます.

例1. 劣ガウシアン性を持つ確率変数

劣ガウシアン性とは裾分布が正規分布のそれ以下のオーダーで減衰していく性質を意味し, 確率集中不等式の文脈では非常に重要なクラスをなします.

定義3 (劣ガウシアン分布).
パラメータ$v>0$に対し, $X$が$v$-sub-gaussianであるとは, 任意の$\lambda\in \mathbb{R}$に対して$\psi_X(\lambda) \le \frac{v\lambda^2}{2}$であることをいう.

簡単に言うと劣ガウシアン性は$\psi_X(\lambda) = O(\lambda^2)$となるような確率変数のクラスです. ちなみに$\psi_X(\lambda) = \log\frac{1}{1-\lambda/a}$の形になっているという性質を劣指数性と呼びます.

さて, 簡単な平方完成から
$$\begin{align*} \psi_X^*(a) &= \sup_{\lambda > 0}\{a\lambda - \psi_X(\lambda)\} \\ &\ge \sup_{\lambda > 0}\left\{ a \lambda - \frac{v\lambda^2}{2} \right\} \\ &\ge \frac{a^2}{2v} \end{align*}$$
を得ます (最後の等号では$\lambda = \frac{a}{v}$を代入).

例2. ポアソン分布

平均$v$のポアソン分布に従う確率変数$X\sim\mathrm{Po}(v)$を考えます. すなわち, 任意の非負整数$k$に対し
$$\begin{align*} \Pr[ X = k ] = \mathrm{e}^{- v} \frac{v^k}{k!} \end{align*}$$
です. このとき, $\psi_X(\lambda) = v(\mathrm{e}^{\lambda} - \lambda - 1)$であり, $\lambda = \log\left( 1+\frac{a}{v} \right)$を代入すると次の凸共役を得ます:
$$\begin{align*} \psi_X^*(a) = v h\left(\frac{a}{v}\right). \end{align*}$$
ただし$h(x) = (1+x)\log(1+x) - x$.

上記のバウンドはBennetの不等式でよく見る形の関数になっています. 有名な不等式として
$$h(x) \ge \frac{x^2}{1+x/3}$$
というものがあります (この形で表現される集中不等式としてBernsteinの不等式と呼ばれる非常に有名なものがあります).

例3. ベルヌーイ試行

$X$を成功確率$p$のベルヌーイ試行とします. すなわち, $X\in\{0,1\}$であり
$$\begin{align*} \Pr[X = b] = \begin{cases} 1 & \text{with probability }p,\\ 0 & \text{with probability }1-p. \end{cases} \end{align*}$$

導出過程は省略(自分で手計算すると簡単に確認できる)しますが,
$$\begin{align*} \psi_X(\lambda)  = \lambda p + \log(p\mathrm{e}^\lambda + 1 - p) \end{align*}$$
となり, $\lambda = \log\frac{(1-p)(p+a)}{p(1-p+a)}$を代入すると凸共役$\psi^*_X(a)$が得られ,
$$\begin{align*} \psi_X^*(a) = (p+a)\log\frac{p+a}{p} + (1-p-a)\log\frac{1-p-a}{1-p} \end{align*}$$
となります. この式の右辺はベルヌーイ試行のKLダイバージェンスと等しいです. $\mathrm{Ber}(p)$と$\mathrm{Ber}(q)$のKLダイバージェンスを$\mathrm{KL}(p||q)$と書くと, この値は
$$\mathrm{KL}(\mathrm{Ber}(p) || \mathrm{Ber}(q)) = p\log\frac{p}{q} + (1-p)\log\frac{1-p}{1-q}$$
で定義され, これを用いると$\psi_X^*(a) = \mathrm{KL}(p+a||p)$と書くことができます. このことから以下のChernoff bound (の特殊ケース)を得ます:

定理4 (Chernoff bound)
$X\sim\mathrm{Bin}(n,p)$のとき, $\Pr[X\ge np + n a] \le \mathrm{e}^{-n\mathrm{KL}(p+a||p)}$.

ここにPinskerの不等式$\mathrm{KL}(p||q)\ge 2(p-q)^2$を代入するとHoeffding boundになります.

解の個数を減らす帰着 (Valiant--Vaziraniの定理)

2月に冬のLAに参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました.

2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。

— Nobutaka Shimizu (@knewknowl) December 22, 2023

自分の発表には全く関係ないことですが, LAに参加していてValiant--Vaziraniの定理がいまいち知名度がないということを初めて認識しました. これまでもこの定理をブログ記事にしたいと常々思っていたので重い腰をあげて解説しようと思います.

充足可能性判定問題 (SAT)とUSAT

$n$個の変数$x_1,\dots,x_n$を持つ論理関数$\phi\colon\{0,1\}^n\to\{0,1\}$が与えられたときに$\phi(x)=1$を満たす$x$が存在するかを問う問題を充足可能性判定問題(SAT)と言います (ここでは論理式は回路として与えられると思ってください. CNFでもOKです.).

一般に充足可能性判定問題は解の存在性を判定するだけです. では特殊ケースとして「充足割当が高々一つしか存在しないことが保証されている論理関数」に対するSATは効率的に解けるのでしょうか？

このような判定問題をUSAT (unique SAT)と言います. 厳密にはUSATは約束問題です. すなわち, 与えられた論理関数$\phi$が以下で定義される二つの集合$U_{\mathrm{yes}},U_{\mathrm{no}}$のどちらに属するかを判定する問題です:
$$\begin{align*} &U_{\mathrm{yes}} = \{\phi\colon \phi\text{ has a unique satisfying assignment}\},\\ &U_{\mathrm{no}} = \{\phi\colon \phi\text{ has no satisfying assignments}\}. \end{align*}$$
与えられた$\phi$がこの二つの集合どちらにも属していない場合はYES/NOどちらを答えても正解としてみなします. $U_{\mathrm{yes}}, U_{\mathrm{no}}$はdisjointですが$U_{\mathrm{yes}}\cup U_{\mathrm{no}}$は必ずしも入力全体の集合になるわけではありません. yesインスタンス全体とnoインスタンス全体の和集合が入力全体になる決定問題を判定問題と呼び, そうとは限らない決定問題を計算量理論では約束問題 (promise problem)といいます (約束問題は判定問題を特殊ケースとして含んでいます). 細かい注意ですが, $\mathsf{P}$とか$\mathsf{NP}$は判定問題の計算量クラスなので「$\mathrm{USAT}\in\mathsf{P}$」という主張は文法がおかしく, 正しくは 「$\mathrm{USAT}\in\mathsf{prP}$」です (promise P).

Valiant--Vaziraniの定理

Valiant--Vaziraniの定理とは乱択を許したときにUSATがSATに帰着できることを主張する定理です. 例えばその帰結として

USATが多項式時間で解ける $\Rightarrow$ SATが乱択多項式時間で解ける

が得られますので, USATはいわば"乱択NP困難" (これはofficialな用語ではない!)ということになります. ValiantはPAC学習を定義したりマッチング数え上げの#P困難性を証明した方で, Vaziraniは近似アルゴリズムの本で有名なVaziraniです. どちらも非常に偉大な方です. 原著論文はこちらです.

定理1 (Valiant--Vaziraniの定理)

論理関数を別の論理関数に変換する多項式時間乱択アルゴリズム$R$とある多項式$p$が存在し, 任意の論理関数$\phi\colon\{0,1\}^n\to\{0,1\}$に対し, 

• $\phi\in \mathrm{SAT}$ ならば, $\Pr[R(\phi)\in U_{\mathrm{yes}}]\ge \frac{1}{p(n)}$.
• $\phi\not\in\mathrm{SAT}$ ならば, 確率1で$R(\phi)\in U_{\mathrm{no}}$.

ただし$\mathrm{SAT}$は充足可能な論理式全体を表す.

仮にUSATが多項式時間アルゴリズム$A$で解けたとしましょう. このアルゴリズム$A$を定理1のアルゴリズム$R$と組み合わせることで以下のようにしてSATを解くことができます:

1. 与えられた論理関数$\phi$を入力として$R$を走らせ, 別の論理関数$\phi'$を得る.
2. $\phi'$を入力として$A$を走らせ, YESを出力したらそのままYESを出力する.
3. そうでなければステップ1に戻る. これを$100p(n)$回繰り返しても終わらない場合はNOを出力する.

上述の乱択アルゴリズムは任意のSATインスタンス$\phi$に対し99%の確率で正解を出力します. 元の$\phi$が$\phi\in\mathrm{SAT}$ならば, $100p(n)$回の繰り返しの中で全て$R(\phi)\not\in U_{\mathrm{no}}$となってしまう確率は$(1-1/p(n))^{100p(n)}\le \exp(-100)<0.01$だからです (ここでは$\forall x\in\mathbb{R},1+x\le \exp(x)$を使っている).

証明のアイデア

証明の直感を養うために, 効率性を無視した次の帰着を考えます:

1. $\phi\colon\{0,1\}^n\to\{0,1\}$を与えられた論理関数とする.
2. 適切に設定されたパラメータ$m$に対し, $f\colon\{0,1\}^n\to\{0,1\}^m$を一様ランダムな関数とする (すなわち, 各$x\in\{0,1\}^n$に対して$f(x)$は独立一様ランダムな$m$ビット文字列を出力する関数.
3. $\phi'(x) = \phi(x) \land \langle f(x)=1^m \rangle$とする. ここで$\langle E \rangle$は事象$E$の指示関数とする.

明らかに, $\phi$が充足可能でないならば$\phi'$もまた充足可能ではありません. 一方で$\phi$が充足可能であるとき, 充足割当の個数を$N$とすると, $\phi'$の充足割当の個数$N'$は$\mathbb{E}[N']=N/2^m$を満たします. ですので, $m=\log_2 N$とすれば期待値が$1$になります. $N'$の実際の分布は二項分布$\mathrm{Bin}(N,1/N)$であり, $\Pr[\mathrm{Bin}(N,1/N)=1]\ge \mathrm{const}$が成り立つ ($N\to\infty$の極限では$\mathrm{Bin}(N,1/N)\to\mathrm{Po}(1)$に収束する). なお, ステップ3の$\langle f(x)=1^m \rangle$における$1^m$は特に$1^m$である必然性はありません.

この帰着では$N$の値を知る必要があるのですが, そこもまたランダムに与えれば良いです. 一様ランダムに$m\sim[n]$をとると確率$1/n$で$2^{m-1}\le N \le 2^m$を満たします. この$m$を用いて上の帰着を実行すれば, 同じようなポアソン近似により確率$\mathrm{const}\cdot (1/n) \ge \mathrm{poly}(n)$で$\phi'\in U_{\mathrm{yes}}$を満たすことが確認できます.

しかしながら, 上述の帰着では一様ランダムな関数$f$をサンプリングするには少なくとも$m2^n$ビットのランダムビットが必要なので, 指数時間かかってしまいます. そこでこのサンプリングに必要なランダムビット数を$\mathrm{poly}(n)$ビットまで削減することを目指していくことになります. すなわち, 一様ランダムな関数と同等の性質を持つ別のランダム関数を短いランダムシード長でサンプリングすることを目標にします.

これはpairwise independent hash functionという, 脱乱択化(derandomization)の分野では標準的な関数を考えることによって解決できます. まず, 確率変数のpairwise independent性について解説します. 

ペア独立性　

この記事では確率変数といえばデフォルトで離散値をとるものを考えます (計算機では全てが離散で処理されるので).

二つの確率変数$X,Y$は, 任意の$x,y$に対して$\Pr[X=x\text{ and }Y=y]=\Pr[X=x]\Pr[Y=y]$を満たすとき独立であると言います. より一般に確率変数$X_1,\dots,X_n$が独立であると言ったとき, それは任意の$x_1,\dots,x_n$に対して
$$\begin{align*} \Pr[X_i = x_i \text{ for all }i\in [n]]=\prod_{i\in [n]}\Pr[X_i=x_i] \end{align*}$$
を意味します. 独立という代わりに相互に独立(mutually indepedent)であると言うこともあります.

一方で, 任意の$1\le i<j\le n$と$x_i,x_j$に対し
$$\begin{align*} \Pr[X_i=x_i\text{ and }X_j=x_j]=\Pr[X_i=x_i]\Pr[X_j=x_j] \end{align*}$$
が成り立つとき, $X_1,\dots,X_n$はペア独立 (pairwise independent) であると言います. pairwise independenceにはこれといったスタンダードな和訳は(私の知る限り)ないと思いますが, ここではこちらのページから拝借しております. なお, 上の定義では$i\neq j$としていることに注意してください.

ペア独立ハッシュ関数

ハッシュ関数と聞くとPythonの辞書などを想起されますが, 計算量の文脈ではハッシュ関数と言ったらある分布に従って生成されたランダムな関数を指すものと思ってください.

ランダムな関数$f\colon\{0,1\}^n\to\{0,1\}^m$に対し, $2^n$個の確率変数$f(0^n),\dots,f(1^n)$がペア独立であるとき, $f$はペア独立ハッシュ関数であると言います.

単に$f$がペア独立ハッシュ関数であると言った場合は単にペア独立性だけを指しますが, しばしば, 任意に固定した$x\in\{0,1\}^n$に対して$f(x)$の分布は一様ランダムであることが多いです.

例えば, 証明のアイデアで考えた「各$x\in\{0,1\}^n$に対し独立一様ランダムな$m$ビット文字列を$f(x)$として出力する関数」はペア独立ハッシュ関数です. この例は生成に指数長のランダムシードを要しますが, よりrandomness-efficientなものも構成できます.

ランダムな直線

有限体$\mathbb{F}=\mathbb{F}_{2^n}$上の関数を考えます. ここでは$\mathbb{F}_{2^n}$の厳密な定義を理解しておく必要はありません. 掛け算と足し算ができて, 非ゼロな元では割り算ができて, これらの演算が$n$に関する多項式時間でできて, しかも$|\mathbb{F}_{2^n}|=2^n$になっているので$\{0,1\}^n$と一対一対応がある, という事実だけを使います. 一様ランダムに$a,b\sim\mathbb{F}$をサンプリングしてランダム関数$f\colon \mathbb{F}\to\mathbb{F}$を
$$f(x) = ax+b$$
で定めます. 有限体を$\mathbb{F}_{2^n}\cong \{0,1\}^n$で同一視すると$f$は$n$ビット文字列から$n$ビット文字列への関数とみなせます.

補題2.

一様ランダムな$a,b\sim\mathbb{F}$に対し, $f\colon x\mapsto ax+b$はペア独立ハッシュ関数である. すなわち, $|\mathbb{F}|$個の確率変数$(f(x))_{x\in \mathbb{F}}$はペア独立である. さらに, 固定した$x\in \mathbb{F}$に対して$f(x)$の分布は$\mathbb{F}$上一様ランダムである.

証明. 任意の$x_1\neq x_2\in \mathbb{F}$と$y_1,y_2\in\mathbb{F}$に対して
$$\Pr[f(x_1)=y_1 \text{ and }f(x_2)=y_2] = \Pr[f(x_1)=y_1]\Pr[f(x_2)=y_2]$$
を示せば良いです. $f(x_i)=y_i$ ($i=1,2$)という等式を行列を用いて表すと
$$\begin{bmatrix} x_1 & 1 \\ x_2 & 1 \\ \end{bmatrix} \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} y_1 \\ y_2 \end{bmatrix}$$
となります. ヴァンデルモンドの行列式から係数行列は正則なので, $[a\,b]^{\top}$はある特定のベクトルになっていなければならず, $a,b\sim\mathbb{F}$は一様ランダムなのでこれが起こる確率は$1/|\mathbb{F}|^2$となります.

一方で$\Pr[f(x_i)=y_i]=1/|\mathbb{F}|$なので, 確かに$(f(x))_{x\in \mathbb{F}}$はペア独立であることが確認されました. (証明終)

補題2で構成したペア独立ハッシュ関数は$n$ビット文字列から$n$ビット文字列への写像でしたが, 出力の$n$ビットのうち最初の$m$ビットだけを取り出した ($m\le n$) 文字列を出力するようにすれば, 値域を$\{0,1\}^m$にしつつペア独立になるようにできます.

補題3.

ペア独立ハッシュ関数$f\colon \{0,1\}^n\to\{0,1\}^n$と固定したパラメータ$m\le n$に対し, $f'(x)\in\{0,1\}^m$を$f(x)$の先頭$m$ビットからなる文字列と定義する. このとき, $f'\colon\{0,1\}^n\to\{0,1\}^m$はペア独立ハッシュ関数である.

証明. 確率変数$(f(x))_{x\in\{0,1\}^n}$がペア独立であることを利用して$(f'(x))_{x\in\{0,1\}^n}$がペア独立であることを示します. ペア独立性の定義から, 任意の$x_1\neq x_2\in\{0,1\}^n$と$y_1,y_2\in\{0,1\}^m$に対して
$$\Pr[f'(x_1)=y_1\text{ and }f'(x_2)=y_2]=\Pr[f'(x_1)=y_1]\Pr[f'(x_2)=y_2]$$
が成り立つことを示せばよいです.

文字列$y\in\{0,1\}^m$に対して, 先頭$m$ビットが$y$になるような$n$ビット文字列の全体を$S(y)\subseteq\{0,1\}^n$とします. $f'(x)$は$f(x)$の先頭$m$文字を取り出すことから, $f'(x)=y \iff f(x)\in S(y)$です. 従って
$$\begin{align*} \Pr[f'(x_1)=y_1\text{ and }f'(x_2)=y_2] &= \sum_{z_1\in S(y_1),z_2\in S(y_2)} \Pr[f(x_1)=z_1\text{ and }f(x_2)=z_2] \\ &= \sum_{z_1\in S(y_1),z_2\in S(y_2)} \Pr[f(x_1)=z_1]\Pr[f(x_2)=z_2] & & \text{pairwise independence of $f$} \\ &= \Pr[f(x_1) \in S(y_1)]\Pr[f(x_2)\in S(y_2)] \\ &= \Pr[f'(x_1)=y_1]\Pr[f'(x_2)=y_2] \end{align*}$$
より主張が得られます. (証明終)

補題2,3を組み合わせると, 以下の命題が成り立つことがわかります.

補題4.

任意の$m\le n$に対し, $\{0,1\}^n$から$\{0,1\}^m$へのペア独立ハッシュ関数$f$であって, 全ての$x\in\{0,1\}^n$に対して$f(x)$の分布が$\{0,1\}^m$上一様ランダムになるようなものが存在する. さらに$x\mapsto f(x)$の計算は$\mathrm{poly}(n)$時間で計算できる.

Valiant--Vaziraniの定理の証明

いよいよ定理1を証明します. $\phi\colon\{0,1\}^n\to\{0,1\}$を与えられた論理関数とし, 以下の帰着を考えます:

1. $m\sim\{1,\dots,n\}$を一様ランダムに選ぶ.
2. $f\colon\{0,1\}^n\to\{0,1\}^m$を補題4で保証されるペア独立ハッシュとする.
3. $\phi'(x)=\phi(x)\land \langle f(x)=1^m\rangle$で定義される論理関数$\phi'$を出力する.

ステップ3では, Cook-Levinの定理の証明からコンピュータで計算できるアルゴリズムはその内部(レジスタや読み込みテープの位置など)の動きを回路で表現できることを用います. すなわち, 補題4では$x\mapsto f(x)$は多項式時間で計算できるので, この計算を回路で表現することによってBoolean関数$x\mapsto \langle f(x)=1^m\rangle$を$n$に関する多項式サイズの回路で表現することができます (SATを考えると, このようにペア独立ハッシュ関数の計算過程を表現できるというuniversalityが役にたつというわけです!). 従って$\phi\mapsto \phi'$を計算する上記の乱択アルゴリズムは多項式時間アルゴリズムです.

正当性の証明

$\phi'$の正当性を証明します. 与えられた論理関数$\phi$が充足不可能ならば$\phi'$を充足する割当も存在しません. 従って$\phi$が充足可能であるときに$\phi'$が充足可能である確率を評価すればよいです.

$\phi$が充足可能であるとし, $1\le N \le 2^n$を$\phi$の充足割当の個数とします. 充足割当が非常に多く, 例えば$N\ge 2^{n-3}$を満たすならば一様ランダムな$x\sim\{0,1\}^n$に対して$\phi(x)=1$かどうかをチェックすれば$\phi$の充足可能性が簡単に解けて, $\phi$が充足可能ならば定数$1$を$\phi'$として出力すればよいので, $N\le 2^{n-3}$を仮定します.

$m\sim[n]$が一様ランダムに選ばれているので, 確率$1/n$で
$$\begin{align} 2^{m-3}\le N \le 2^{m-2} \end{align}$$
を満たします. 以後は$m$が(1)を満たすと仮定して議論を進めます.

$\phi$の充足割当の全体を$a_1,\dots,a_N$ ($a_i\in\{0,1\}^n$) とし, 確率変数$X_i=\langle f(a_i)=1^m \rangle$を考えると, $X=\sum_{i\in[N]} X_i$は$\phi'$の充足割当の個数に等しいです. ですので $\Pr[X=1]\ge 1/\mathrm{poly}(n)$を示すのが目標です. $N$と$m$の関係(1)より, $1/8 \le \mathbb{E}[X] \le 1/4$です.

任意の$x\in\{0,1\}^n$に対して$\Pr[f(x)=1^m]=1/2^m$なので, $\mathbb{E}[X]=N/2^m$を満たします. 従って
$$\begin{align*} \Pr[X=1] &= \Pr[\exists i,X_i=1\text{ and }\forall j\neq i,X_j=0] \\ &= \sum_i \Pr[X_i=1\text{ and }\forall j\neq i,X_j=0] \\ &= \sum_i \Pr[\forall j\neq i,X_j=0\,|\,X_i=1]\Pr[X_i=1] \\ &= \sum_i (1-\Pr[\exists j\neq i,X_j=1\,|\,X_i=1])\Pr[X_i=1] \\ &\ge \sum_i \Pr[X_i=1] (1-\sum_{j\neq i} \Pr[X_j=1\,|\,X_i=1]\Pr[X_i=1]) \\ &= \sum_{i}\Pr[X_i=1]-\sum_{i\neq j} \Pr[X_i=1]\Pr[X_j=1] & & \text{pairwise independence}\\ &\ge \mathbb{E}[X] - \mathbb{E}[X]^2 \\ &\ge \frac{1}{8} - \frac{1}{16} & & \text{(1)}\\ &\ge \frac{1}{16} \end{align*}$$
を得ます. $m$が一様ランダムなので, (1)が成り立つ確率は$1/n$です. 従って, $\phi$が充足可能のときに$\phi'\in U_{\mathrm{yes}}$となる確率は少なくとも$\frac{1}{16n}$となります. (証明終)

グラフ問題に対するペア独立性の応用

Valiant--Vaziraniの定理はSATに対してペア独立な関数を制約に加えることによって解の個数を減らすという帰着でしたが, 似たようなアイデアに基づいてグラフ上の部分グラフ数え上げ問題に対して解の個数を減らす帰着を与えることができます (ただし帰着後の問題は元の問題とは違う問題になってしまう).

次の二つの問題を考えます:

1. 与えられたグラフ$G=(V,E)$が三角形を含むかどうかを判定せよ ($\mathrm{TRI}$)
2. 有限体$\mathbb{F}_q$に対し, 各辺$e\in E$が$\mathbb{F}_q$の元を重みとして持つ辺重みグラフ$\tilde{G}$を考え, 辺重みの総和が$0$になるような三角形（以後はゼロ三角形と呼ぶ) の存在性を判定せよ ($\mathrm{ZWT}_q$)

問題1は隣接行列の三乗を計算して対角成分を見ればよいので$O(n^{\omega})$時間で計算できます. 問題2は精緻な計算量 (fine-grained complexity) の文脈で難しい問題とされていて, $q$が十分大きいときは任意の定数$\varepsilon>0$に対して$O(n^{3-\varepsilon})$時間で解けないと予想されています. ですので, 本質的には$\mathrm{TRI}$と$\mathrm{ZWT}_q$の間にはギャップがありそうだと思われており, $\mathrm{ZWT}$の方が難しいと思われています.

ここで, 問題2においてゼロ三角形が高々一つであることを保証する問題を$\mathrm{UZWT}$とします. $q\approx 3\log n$のとき, $\mathrm{TRI}$から$\mathrm{UZWT}_q$への乱択帰着が存在します.

証明のアイデア. 与えられた$\mathrm{TRI}$のインスタンス$G=(V,E)$に対し, 各辺に$\mathbb{F}_q$上一様ランダムな重みを付与したグラフ$\tilde{G}=(V,\tilde{E})$を考えます.　$G$の各三角形$(u,v,w)$に対し, この三角形が$\tilde{G}$においてゼロ三角形になる確率は$1/q^2$です. なので適当な範囲から$q$をランダムに選ぶと, ある程度の確率で$q^2$が$G$の三角形の個数と大体同じくらいになります. また, $G$の三角形$T$に対して$X_T$を三角形$T$が$\tilde{G}$においてゼロ三角形になるかどうかの指示関数とすると, $(X_T)_T$はペア独立になります！

この事実を確認するために, 相異なる二つの三角形$T\neq T'$を考えます. $T$と$T'$が辺を共有しない場合は$X_T$と$X_{T'}$は独立です. 仮にこの二つの三角形が辺を共有していたとしても, $T\neq T'$より共有している辺の本数は必ず$1$本になり, これ以外の辺の重みは独立に決まるので$X_T$と$X_{T'}$は独立になります.

従って, ランダムに重みを付与したZWTのインスタンス$\tilde{G}$はある程度の確率でゼロ三角形を唯一含みます.