SODA21に論文が2本通りました (1/2)

論文が SODA21 (Symposium on Discrete Algorithms) に 2本採択されました。

・Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH

Shuichi Hirahara and Nobutaka Shimizu

arXiv

・How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?

Shuji Kijima, Nobutaka Shimizu, and Takeharu Shiraga

arXiv

の2本です。どちらの論文も非常に面白い内容で、嬉しいことに全ての査読者にかなり褒めて頂きました。

この記事では、前者の論文

Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH

の概要をものすごく簡潔に紹介します。

この論文はNIIの平原 秀一さんとの共著です。今年の2月に 冬のLA symposium で発表させていただいた内容を論文としてまとめたものになっています。

この論文は「ランダムグラフの tractability」が主要なテーマです。NP困難な問題は "intractable" であるというイメージを持つ方が多いと思います。しかしながらNP困難であるからといって実用的に解けないというわけではないはずです。なぜならば、その問題がNP困難であるとは、$\mathrm{P}\neq \mathrm{NP}$の下で

任意の多項式時間アルゴリズム $A$ に対し, ある入力の族 $(x_n)_{n\in\mathbb{N}}$ が存在して 全ての$n\in\mathbb{N}$に対し$A(x_n)$は不正解となる

ことを主張しているに過ぎず、つまるところ意地悪な入力 $x_n$ は非常に人工的に構成されたものになるからです。ですので、現実世界にしばしば現れるような入力ではもっと高速に解ける可能性があるはずです！

ということは、問題の時間計算量を、「全ての入力に対し正解する最速のアルゴリズム」ではなく「多くの入力に対して正解する最速のアルゴリズム」で測るという考え方がより実用性に近いと思われます。この考え方を平均計算量といいます。平均計算量のより詳しいフレームワークはこちらを参照してください。

この論文では、「$n^{c+o(1)}$ 時間で解けるとあるグラフ上の問題に対し, (SETHと呼ばれる予想の下で)ランダムグラフ上ですら $n^{c-\epsilon}$ 時間では解けない 」ことを証明しました。具体的には、ランダム二部グラフが入力として与えられたときにそれに含まれる完全二部グラフ $K_{a,b}$ と同型な部分グラフの個数を数え上げる問題を考えます。この問題は愚直にやると $O(n^{a+1})$ 時間で解くことができます (頂点を $a$ 個列挙し、その$a$個全てに隣接している頂点を列挙すれば良い)。また、例えば $a=b=2$ の場合だとこれは四角形の個数をカウントする問題になりますが、これは現状知られている中では $O(n^{\omega})$ 時間が最速です ($\omega <2.373$ は高速行列積の指数). この論文では $K_{a,b}$ 数え上げ問題に対し、

(i). $a\geq 8$ なら $bn^{a+o(1)}$ 時間で解けることを証明

(ii). SETHの下では任意の $\epsilon>0$ に対し, 十分大きな $b=b(a,\epsilon)$ が存在して $K_{a,b}$ の数え上げは$n^{a-\epsilon}$ 時間では解けないことを証明

(iii). ランダム二部グラフ上で $T(n)$ 時間で解けるならば、全ての入力に対し $T(n)\mathrm{polylog}(n)$ 時間で解く乱択アルゴリズムが存在することを証明

しました。

SETH に関しては Hardness in P について紹介しているこちらのページを参照ください。

（ここから先は専門家向けの説明になります）

実はこの論文の最大の貢献は、fine-grained average-case complexity に hardness amplification の枠組みを提供したことにあります。hardness amplification は 平均計算量の世界ではかなりスタンダードなツールなのですが、local list decoding なので uniform な計算モデルで考えようとすると advice が必要になり、fine-grained な世界には実は愚直には適用することができません。しかし、今回のような数え上げの問題のように良い性質を持つ問題ならば適用することができる、というのが最大のウリです。