アルゴリズムの理論研究の最高峰とは?

競プロで道具として用いられる様々な賢いアルゴリズムやデータ構造の多くは, 非常に賢い研究者たちによって発見されており, ほとんどは理論計算機科学の論文として国際学会の会議録や学術雑誌の形として出版されています. ここではアルゴリズム系の研究論文がよく出てくる様々な国際会議を紹介します. ちなみに各国際会議は基本的に年1回の頻度で開催され, そのために我々研究者はがんばって研究して論文を締め切り前に間に合わせるという「論文執筆マラソン」をしています. ちなみに以下の説明では「(会議名)に論文を通す」という言い方をしますが, これはその会議に論文が採択されるということを意味します.

以下に重要な注意事項を書き添えておきます:

• 国際会議は基本的に複数人(大体3人くらい)による査読の評価によって採択の可否が決定されます. 一般に査読の期間は1ヶ月程度であることが多いため, 細かい証明の隅々まで読まれることは稀です. そして査読者がその論文の文脈のエキスパートであることもあれば, そうではない可能性もあります. 従って, 運良くエキスパートに査読を引き受けてもらえた場合は精度の高い評価を下されることが期待されますが, そうではない可能性もそれなりに大きく, その時は正当な評価が下されない可能性もあります (そもそも証明が間違っているけど見逃されて通る可能性だってあります). ですので, 採択の可否にはある程度の運要素が絡んでくることもあることを念頭においてください (こうならないよう, 論文では誰にとっても分かりやすく背景やその手法の凄さをアピールするなどの工夫を凝らす必要があるのです). 
• 凄い会議に論文を通すことは誉れの一つではあるものの, それが凄さの指標の全てでは決してありません. 大学の運営業務や講義などの間の時間を縫って, 学会やシンポジウムの運営, 本の執筆, 研究予算を獲得し学生の旅費を捻出して学生を育成するなど, 様々な形で分野に多大な貢献をしている先生は多くいらっしゃいます. あなたが学生であるならば, あなたの指導教員はマジでめちゃくちゃ凄い人です. ぜひ仲良くしましょう. ついでに将来偉くなる可能性があるので私とも仲良くしましょう.
• 以下では非常にレベルの高い国際会議を紹介して「めちゃくちゃすごい」と言っているだけですが, 私個人の意見としてはこれらを過度に神格化せず, 実は「意外と手の届くところにある」という認識を持って臆せずチャレンジし続けるべきだと思います.

1.Symposium on Theory of Computing (STOC)

理論計算機科学で最もレベルが高い国際会議は二つあり, そのうちの一つがSTOCという国際会議です. 例えばNP完全性の概念を導入したCook (1971)はSTOCの論文です. STOCのスコープは理論計算機科学全般であり, 例えばSTOC2025のcall for paperには

Papers presenting new and original research on the theory of computation are sought. Typical but not exclusive topics of interest include algorithms and data structures, computational complexity, randomness in computing, algorithmic graph theory and combinatorics, analysis of Boolean functions, approximation algorithms, cryptography, computational learning theory, continuous and discrete optimization, economics and computation, parallel and distributed algorithms, quantum computing, algorithmic coding theory, computational geometry and topology, computational applications of logic, algebraic computation, and computational and foundational aspects of areas such as machine learning, fairness, privacy, networks, data management, databases and computational biology. Papers that extend the reach of the theory of computing, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged. The program committee will make every effort to consider a broad range of areas. The program committee will make every effort to consider a broad range of areas.

とあります. STOCに採択されるためには凄い証明を使って強い結果を示しつつ, その結果の背景とインパクトをアピールし, さらにその証明アイデアをめちゃくちゃ分かりやすく説明するなど, 非常に多大な努力を伴います. そのため, STOCに採択されることは理論計算機科学の研究者にとって最も栄誉なことであると同時に, 何度もSTOCに通している人はその研究トピックに関する世界的なエキスパートの一人であると認識されていきます.

ちなみに自分が2024年に参加したときは賢いアルゴリズムを提案する論文よりも計算量下界を導出した論文の方が採択される率は高いということを運営の方が発表していました.

2. Symposium on Foundations of Computer Science (FOCS)

先ほど述べた「理論計算機科学で最もレベルが高い国際会議」の二つのうちのもう一つがFOCSという国際会議です. 内容的には基本的にSTOCと同じなのですが, 違いはスポンサーにあり, STOCはACM SIGACTによってサポートされていて, FOCSはIEEEによってサポートされています. FOCS2025のcall for paperはSTOC2025とほぼ同じです:

Papers presenting new and original research on theory of computation are sought. Typical but not exclusive topics of interest include: algorithmic coding theory, algebraic computation, algorithmic graph theory, algorithmic game theory, algorithms and data structures, analysis of Boolean functions, approximation algorithms, average-case complexity, computational applications of logic, combinatorics, computational complexity, communication complexity, circuit complexity, combinatorial optimization, computational game theory, computational geometry, computational learning theory, continuous optimization, cryptography, foundations of machine learning, online algorithms, optimization, parallel and distributed algorithms, parameterized algorithms, randomized algorithms, sublinear algorithms, streaming algorithms, quantum computing, pseudorandomness and derandomization, foundations of fairness and privacy, and theoretical aspects of areas such as networks, information retrieval, computational biology, and databases. Papers that broaden the reach of the theory of computing, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged.

STOCとFOCSはどちらもほぼ同程度にレベルが高く, その採択は非常に誉高い業績とされています. ちなみにアルゴリズム系と一口にいってもSTOCやFOCSでは暗号や量子計算の話もよく出てきます.

3. Symposium on Discrete Algorithms (SODA)

SODAはSTOC/FOCSと比較するとややレベルは落ちるものの, それでもなお非常にレベルの高い国際会議です. タイトルにあるように離散アルゴリズムに関する国際会議ですが, 実際のところはグラフといった離散構造の論文や計算量下界の論文もあるので, まぁなんでもありの会議です (例えば自分はアルゴリズムが全く出てこない論文を通したことがあります).

SODA, STOC, FOCSの三つはまとめて理論系のトップ会議として言及されることが多々あります.

• 理工学部教授 浅野孝夫 最終講義「離散アルゴリズムと国際会議STOC・FOCS・SODAとの出会いから」を開催
• 理論系(STOC, FOCS, SODA)からビッグデータ・AIのトップ会議へ
• JST ERATO巨大グラフプロジェクト２０１２－２０１７ 総括と遺言
• 河原林健一氏の日本学士院学術奨励賞受賞に寄せて

特に三つ目のスライド資料はとても面白いのでぜひ眺めてみてください. 河原林先生のSTOC, FOCSへの情熱が感じられます. また, 四つ目のリンクでは, 徳山 豪 先生は「日本人研究者では，生涯に 1 つ論文が載ればかなり優秀で，複数の論文を持つ研究者は数えるほどしかいない．」と述べています.

なお, アメリカとかだと凄い先生の下で一緒に論文を書いてたくさんSODA, STOC, FOCSに論文を通すという学生は結構いるのですが, 残念ながら日本では(大学教員の多忙さも相まって)そのレベルの研究をコンスタントに実行できる凄い先生がほとんどいないこともあり, 日本でSODAに論文を通す学生は2,3年に一人いるかどうか, STOC/FOCSに通す学生は5,6年に一人いるかどうかだと(個人的な感覚ですが)思っています. ちなみにSODA, STOC, FOCSにはたまに競プロの凄い人も発表していることがあり, Google Code JamのTシャツとかを着てる人を何回か見かけたことがあります.

他の会議

なお, 他にも理論計算機科学の分野の国際会議は非常にたくさんあります. 自分がすぐ思いつくだけでもICALP, ESA, CRYPT, SoCG, PODC, DISC, QIP, MFCS, CCC, SOSA, RANDOM, APPROX, WALCOM, ISAAC, ISSAC, STACS, IPCO, SPIRE, SAT, IPECなどがあります (他にももっとあります. メジャーなもので抜けてるものがあったら追加するので教えてください).

SODA, STOC, FOCSが別格というだけでこれらの中にもとてもレベルの高い国際会議はいくつかあります. 例えばPODC (Symposium on Principles of Distributed Computing) は分散計算にフォーカスを絞った国際会議で, CCC(Computational Complexity Conference)は計算量下界に関する国際会議です (いずれもレベルの高い会議として認識されています). 個人的にはランダムネスに関する会議RANDOMが好きです. トピックが絞られているが故の利点もいくつかあります:

• 自分の専門に近い査読者に査読がいきやすい
• 参加するとそのコミュニティと繋がりやすい
• そもそも自分の専門分野に近いので面白い発表が多い

また, 他にもアルゴリズム全般を扱う汎用的な国際会議はICALP (Track A), ESA, MFCS, WALCOM, ISAACなどがあり, 学生の国際学会発表の経験を積むという点でも非常に重要な役割を果たします. 人によって色々ありますが, 私の認識ではこれらの中ではICALP (Track A)が頭一つ抜けているイメージです (他の会議はどんな感じなのか本当に何も知らないので何かご存知のことがあったらXかリアルで会ったときに是非教えてください). これらの中にも歴史的な論文は多くあります. 例えば行列積の検算を乱択で行うFreivaldsのアルゴリズムはMFCS(1979)に採択された論文に登場しています).

なお, 全ての国際会議に共通して言えることですが, 論文の採択可否の決定や現地での運営など, 非常に多くの人の多大な協力によって開催されています. 国際会議に参加する際は, その裏にはそういった努力があることをぜひ念頭において, 楽しみましょう!

ざっくり解説: 焼きなまし法はなぜうまくいくのか？

概要

焼きなまし法は遺伝的アルゴリズムなどと並ぶ最適化問題の発見的解法の一つとして有名であり, 競技プログラミングの文脈ではマラソン(厳密解を求めるのが困難とされる一つの最適化問題に長時間取り組み最も最適値に近い解を得るという種目) においては常套手段の一つとして用いられています. 従ってこの文脈では様々な解説記事があるのですが, いわゆるマラソン競技特有の「コツ」や実装方法の説明がほとんどで, 焼きなまし法自体を数理的に深掘りした記事もなくはないのですが, やはり「なぜうまくいくのか」の観点で説明している記事はほとんど見たことがないので, なんとなくこの辺りが気になるという人向けにこの記事で解説していきます (公開時は把握してなかったのですが, 本記事の内容はこちらの記事とほぼ同じ内容になっていますので, 数理的な説明をする記事が全くないというわけではありません). 内容としてはメトロポリス・ヘイスティング法の説明になりますが, 数学的な厳密性は犠牲にして自分の理解で執筆していますので, 厳密な議論まで気になる方は論文を読んでください (もしかしたら他の説明の仕方があるかもしれません).

結論から述べると

• 焼きなまし法は, 遷移確率が時間とともに変動するランダムウォークを実用的な観点から修正したものとみなすことができる.
• このランダムウォークは, 遷移確率の変動が各時刻において十分に微小であれば, そのランダムウォークの収束先は最適解上の分布になることが保証される.
• しかし, 理論的に保証される収束は非常に遅いため, 実用の場面では, 適当なところでランダムウォークを打ち切ったり, より良い解を得るための(理論保証のない)修正を施す. これがマラソンなどの場面でよく見かける焼きなまし法である.

この記事にアクセスする人は焼きなまし法についてはなんとなく知ってるということを仮定します. ただ, 念の為, 初見の人にもアクセスできるよう, 焼きなまし法に関する説明を次の章で与えておきます. 焼きなまし法を知っている人はその次の2章までスキップして構いません.

1. 焼きなまし法とは?

焼きなまし法とは最適化問題に対し, 最適に近いであろう実行可能解を得る手法の一つで, 局所探索と呼ばれるカテゴリーに属します. 局所探索とは, 何かしらの実行可能解を一つ用意し, その解を逐次更新していくというアルゴリズムの総称であり, 焼きなまし法以外には山登り法などが知られています. ここでは以下の記法を用います.

• 実行可能解全体の空間は有限集合とし記号$S$で表します. 
• 実行可能解を$x,y,z\in S$などと表します
• 目的関数値を$f\colon S \to \mathbb{R}_{\ge 0}$で表し, 最小化を目指すこととします.
• 実行可能解$x\in S$の近傍集合を$N(x) \subseteq S$とし, その要素$y\in N(x)$を近傍と呼ぶ.

すなわち, $S$という有限集合と$S$上に非負値をとる関数$f$があり, $f(x)$が最小となる$x\in S$を見つけることが目的となります. 直感的には近傍$y \in N(x)$は$x$と「ちょっとだけ違う実行可能解」です. 実行可能解と目的関数の定義は考える最適化問題に依存しますが, 実行可能解はアルゴリズムの設計者が定義するため, 同じ最適化問題であっても様々な近傍を考えることができます.

山登り法では, 現在の実行可能解$x\in S$に対し, $f(y)$が最小となる近傍$y\in N(x)$を選び, それを$x$に置き換えて同じ処理を繰り返すというアルゴリズムです (または$N(x)$の元$y$を順番に一つずつ見ていき, $f(x)>f(y)$を満たす近傍$y$が見つかったらその瞬間に$x:=y$とするようなものも考えられる. これは, $|N(x)|$の要素数が非常に大きい時は$\min_{y\in N(x)} f(y)$を計算に時間がかかる際に有効な方法である).

このアルゴリズムだと谷底 (全ての近傍の目的関数値が今の解より真に良くならないような解; 局所最適解と呼ぶ) にいきつくとそれ以上動かなくなるのでアルゴリズムは終了します. 上図の例では偶然にも最適解に辿り着きますが, 一般に谷底は複数あり, どの谷底に至るかは一番最初に選んだ解に依存するため, 最適性の保証はありません (ただし空間が連続的で目的関数値が凸性を持つなど, 特定の状況下では最適性が保証できます).

一方, 焼きなまし法では, 現在の実行可能解$x\in S$に対し, 近傍$y\in N(x)$を順番に見ていき,

1. 目的関数値が改善, すなわち$f(x)>f(y)$を満たすとき, $x:=y$として次の反復へ移行
2. そうでない場合, $f(x),f(y)\in\mathbb{R}_{\ge 0}$, そしてこれまでの反復回数$t$のみから定まるある確率$p$で$x:=y$として次の反復へ移行

というアルゴリズムです. 例えば$p=0$ならば山登り法に一致します.

焼きなまし法では確率的に登ることがある.

ここで確率$p$は

$$ p = \exp\left(-\frac{f(y) - f(x)}{T}\right) \tag{1} $$

とします. ここで$T=T(t)>0$は温度と呼ばれるパラメータであり, これまでの反復回数$t$の関数であり, $t\to\infty$としたとき$T\to 0$となります. ここで, $f(y)\ge f(x)$を仮定しているため常に$p\in[0,1]$です.

確率$p$については以下の観察ができます:

• 解の改悪幅$f(y)-f(x)$が大きいほど$p$が小さい, すなわち$x\to y$の遷移が発生しにくい.
• 改悪幅を正の値で固定したとき, 温度$T$が$0$に近いほど$p$は小さくなります. つまり, $T$が大きいときは改悪($f(x)<f(y)$なる$y\in N(x)$への更新)が発生しやすくなるが, 反復を繰り返し$t\to\infty$としていくと$T\to 0$に近づくため, より山登り法に近い振る舞いをするようになる.

温度$T(t)$の定め方は「非常にゆっくり$T\to 0$に収束する関数」であることが理想ですが, 実際に焼きなまし法を走らせる際は手っ取り早く良い解を得たい場合がほとんどなので, あらかじめ反復回数を決定しておき, 最終的に$T\approx 0$になるように線形で下がっていくようなものを考えることもあります. ただし理論的な保証があるのは「非常にゆっくり」収束するという条件が必要なので, この時点で理論保証から外れてしまうことになります.

2. メトロポリス-ヘイスティング法

突然ですが, 有限集合$S$上の関数

$$ f\colon S \to \mathbb{R}_{\ge 0} $$

が定まっているとき, $f(x)$を最小にする$x\in S$を求めるにはどうすれば良いでしょうか? 唐突ですが, 温度と呼ばれるパラメータ$T>0$に対して$S$上の確率分布$\pi\in[0,1]^S$を以下で定めます:

$$ \pi (x) = \frac{\exp(- f(x)/T)}{Z}. \tag{2}$$

ここで$Z = \sum_{x\in S}\exp(-f(x)/T)$は$\pi$を分布に正規化する値 (様々な文脈で分配関数と呼ばれる値) です. また, この分布$\pi$を(エネルギー$f$に対する)ボルツマン分布と呼ぶらしいです.

分布$\pi$に従って生成される確率変数$X \sim \pi$を考えると, 以下の観察が芽生えます:

• 温度$T$が非常に大きい値, 極端に言えば$T=\infty$ のとき, $f(x)$の影響は無視されるため, $\pi$は$S$上で一様ランダムとなります.
• 温度$T$が非常に小さい値, すなわち$T\approx 0$ のとき, $\pi$は最適解$S^*=\{x\in S\colon f(x) = \min_{y\in S}f(y)\}$上の一様分布となります.

従って, 理想的には$T\approx 0$において$\pi$に従う確率変数を生成できれば最適化問題を解いたことになります!! ところが, 分配関数$Z$が簡単に計算できそうな見た目をしてないので, $\pi$に従う確率変数をサンプリングするということ自体が非自明なタスクになっています. メトロポリス-ヘイスティング法とは, 目標となる分布$\mu$があったとき, ランダムウォークを用いてこの分布に非常に近い分布に従う確率変数を生成する手法の一つです.

具体的には, $S$上の何らかのランダムウォークの遷移確率行列$P \in [0,1]^{S\times S}$が与えられているとします. ここで$P(x,y)$は$x$から$y$に遷移する確率を表しており, 例えば焼きなまし法の例でいうと, 一様ランダムな近傍に遷移する, というランダムウォークだと思えばOKです. 一般にランダムウォークはその遷移がとある条件 (例えば遷移の強連結性など) を満たせば, 定常分布と呼ばれるある分布に収束するという事実が知られています. 今考えているランダムウォーク$P$もその条件を満たしているとします. ただし$P$の定常分布は目標としている分布$\pi$とは異なっていることもあります.

メトロポリス-ヘイスティングス法のイメージ

メトロポリス-ヘイスティング法とは, 手元にあるランダムウォーク$P$に適当な重さの自己ループの追加などにより修正し, 目標分布$\pi$を定常分布とするような別のランダムウォーク$P'$をうまく定めるという手法です.

より詳細を述べると, 修正後のランダムウォーク$P'$は以下のような形をしています: ランダムウォーク$P$により, $x\to y$という遷移が発生したとき, 確率$a(x,y)$でその遷移を受理し実際に遷移し, 確率$1-a(x,y)$でその遷移を拒否し$x$にとどまる.

簡単のため$P(x,x)=0$とすると, $P'\in[0,1]^{S\times S}$の成分は

$$
P'(x,y) = \begin{cases}
P(x,y)\cdot a(x,y) & & \text{if }x\ne y,\\
1-\sum_{y} P(x,y)\cdot a(x,y) & & \text{otherwise}
\end{cases}
$$

となります. 肝心の受理確率$a(x,y)$の定め方ですが, $P'$が定常分布$\pi$を持つように, そして$a(x,y)$の値ができるだけ大きくなるように (自己ループの確率が少ない方が遷移する回数が多くなるため) 設計します. 詳細は省きますが釣り合い条件と呼ばれる条件から, $P'$は次の等式

$$ {}^{\forall} x,y\in S,\quad\pi(x) P'(x,y) = \pi(y) P'(y,x) $$

を満たしていなければなりません. これに$P'$の成分を代入すると

$$ \pi(x) a(x,y) P(x,y) = \pi(y) a(y,x) P(y,x) $$

となります. 

計算の簡単のため, $P$が対称行列だとしましょう. すると上の等式は$\pi(x)a(x,y) = \pi(y)a(y,x)$となります. ここで, できるだけ$a(\cdot,\cdot)$の値を大きくとると, 片方は$1$に設定できます. 従って

\begin{align*}
&a(x,y) = \min\left\{ \frac{\pi(y)}{\pi(x)},\,1\right\},\\
&a(y,x) = \min\left\{ \frac{\pi(x)}{\pi(y)},\,1\right\}
\end{align*}

を得ます. このようにして定まる受理確率$a(x,y)$は$\pi(x)$と$\pi(y)$の比のみに依存するという素晴らしい性質を持っています. 実際, $\pi$が(2)のような形になっているとき, その比は分配関数$Z$に依存せず,

$$ \frac{\pi(y)}{\pi(x)} = \exp\left( - \frac{f(y)-f(x)}{T} \right) $$

で簡単に計算できます. この値はまさに(1)で考えていた値と一致します. つまり, 焼きなまし方とは, メトロポリス-ヘイスティングス法の受理確率を模した確率的な遷移を許容する局所探索といえます.

なお, 実際の焼きなまし法では温度パラメータ$T$は遷移回数とともに変動します. 直感的にはこの変動は十分ゆっくりであれば局所的には$T$が固定された値とみなせるので解析できそうですが, この直感を厳密な形にするにはそれなりの苦労が必要のようです (例えばこの記事. この辺は私もまだわかっていない)

なお, メトロポリス-ヘイスティングス法で得られるランダムウォーク$P'$は, 収束先の定常分布が$\pi$であるということのみが保証されるため, その収束の速さについては何も保証がありません. しかし, 適当な仮定の下では何かしらの収束時間のバウンドを与えることは可能となります.

3. まとめ

冒頭にも述べましたが, 要するに

1. 最適化問題を解くというタスクをある目標分布に従うサンプリングに置き換える
2. このサンプリングタスクをメトロポリス-ヘイスティング法で解く
3. プロセス1,2の構造をできるだけ保ちつつ, 実用的に手っ取り早く良い解を得るための工夫を施して実装したものが焼きなまし法である

ということになります (もしもうちょっと深い理論の話があったら教えていただけると幸いです). 

なお, 最適化問題は$f$が凸性を持つときは「局所最適解は最適解の一つである」が成り立つため非常に解きやすくなるのですが, 同様に分布$\pi$は対数凹性を持つときはサンプリングしやすいという事実があるようです. 実際, $f$が凸のとき, 対応するボルツマン分布$\pi$は$\log \pi(x) = -\frac{f(x)}{T}$より, 対数凹性を持ちます.

講義資料を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な部分集合族はひまわりをなすので, これで定理の主張が証明できたことになります.