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