FCRC 2011参加報告

吉田です。

先日、アメリカのサンノゼで開催されたFCRC (Federated Computing Research Conference)に参加してきましたので、その様子について報告したいと思います。

写真は最終日に遊びに行ったスタンフォード大学の門です。奥に見える(見えない？)建物まで歩かないとキャンパスに辿り着きません。アメリカの広さを感じます。

FCRCはACM(アメリカの計算機科学に関する学会)によって4年に一度開催されるイベントで、そこでは15個程度の会議が同時開催されます。会議のジャンルは多種多様で、理論計算機科学(CCC/STOC/EC)、並列/分散アルゴリズム(PODC/SPAA),プログラミング言語(PLDI)、ハイパフォーマンスコンピューティング(HPDC)などなど何でも有りです。これらの会議が並列に一週間以上に渡って開催されました。

• 全体の流れ

基本的に各会議は別の部屋でバラバラに開催されているのですが、毎日一回招待講演が有って、そこでは広いホールに数千人の人が集まります。

例えば今回のFCRCでは

1. Leslie Valiant: チューリング賞受賞記念講演
2. David Ferrucci: IBM Watson(質疑応答システム)のプロジェクトマネージャー
3. Ravi Kannan: クヌース賞受賞記念講演

などが有りました。

残念ながらValiantの講演は聞き逃したのですが、噂によると進化論とコンピュータを結びつけると言う、かなり突飛な話だったそうです。個人的にはこういう突飛なことを偉い人がするのは大歓迎です。チューリング賞を取るような人は、もう普通の研究をして知名度を上げる必要性も無いので、どんどん新しい分野を開拓してほしいと思います。

Ferrucciの講演は開発の経緯や苦労話が中心でした。ワトソンの管理に特化したバグトラッキングシステムのようなものが有るらしく、どの手法を使うと、どういう質問に対して、どういう答えが出るかが一目で見れるようになっていたのが印象的でした。最終的に8000通りぐらいの手法を試したらしく、その馬力に驚かされます。自前のシステムを作り、様々な手法を試して、少しずつ精度を上げるというのは、まるで長期戦のプログラミングコンテストに取り掛かっているかのようでした。個人的には技術的な詳細にも興味が有ったのですが、一時間の講演ではそこまで語る余裕は無かったようです。

Kannanの講演はかなり理論計算機科学よりだったと思います。要約すると、一見幾何と関係ないものも、幾何的に見ると本質が見えることがある、というものでした。自然言語処理の世界では、よく文書を単語を要素とするベクトルで表現しますが、そう言う話の延長です。

周りの人を観察していると、会議に参加して講演を聞いている人は半分、会議場の外で知り合いと話をしている人が半分と言ったところでした。当たり前ですが、みんな研究が本当に好きで、周りの人の雑談を聞いていると大体polynomialという単語が聞こえてきます(笑)。僕自身も大体同じで、講演をずっと聞いていたというよりは、知り合いと話をしている時間の方が長かったように思います。丁度、直前にSublinear Algorithm 2011というワークショップに参加していて、そこで知り合った人が多数来ていたので、話す相手には困りませんでした。

また廊下では色々な会議のポスターセッションが催されていて、他分野でどんな研究がされているのかを知る良い機会となりました。ポスターは分からないことが有ればじっくり話が聞けるので、講演とは又違う良さがあります。

• STOC/CCC

FCRCの中で理論計算機科学に分類されるであろう会議は

1. STOC (Symposium on Theory of Computing)
2. CCC (Conference on Computational Complexity)
3. EC (Conference on Electronic Commerce)
4. PODC (Symposium on Principles of Distributed Computing)
5. SPAA (Symposium on Parallelism in Algorithms and Architectures)

が有りました。そのうち僕はSTOCとCCCで発表が有ったので、主にこの二つの会議の講演を聞いていました。その中でいくつか印象に残ったものを書きたいと思います。

* The Power of Simple Tabulation Hashing by Mihai Patrascu and Mikkel Thorup

ハッシュは言うまでもなく重要なデータ構造です。ハッシュの中で起こる競合の回数を抑える為に、ハッシュ関数\(h\)の設計が重要になります。ここで\(x_1,\ldots,x_k\)がランダムに分布すれば、\(h(x_1),\ldots,h(x_k)\)もランダムに分布するとき、\(h\)を\(k\)-wise独立と呼ぶことにします。

一般的に\(k\)が大きい程便利なのですが、\(k\)が大きいハッシュ関数は一般に計算コストが大きいという問題があります。この論文では、このハッシュ関数の設計をtabulationと呼ばれる単純な手法に置き換えても、多くの応用で\(k\)が大きいハッシュ関数と同等の振る舞いをすることを示しています。

実際に実験も行っており、それを見る限り既存の手法と比べて\(10\)倍近くのスピードアップになっていました。最近のアルゴリズムは、理論的な保証は良いものの複雑すぎて実装できない、ということがよく有ります。それに対して、この論文のアルゴリズムは実装がとても単純で、

解析は複雑というアルゴリズムの研究のあるべき姿を示していると思いました。

* Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs by Paul Christiano and Jonathan A. Kelner and Aleksander Madry and Daniel A. Spielman and Shang-Hua Teng

\((s,t)\)-最大流とはグラフ理論の最初の方で学ぶ基本的な組合せ最適化問題です。この論文では\((s,t)\)-最大流の\((1-\epsilon)\)近似を\(\widetilde{O}(mn^{1/3}\epsilon^{-11/3})\)時間で計算するアルゴリズムを示しています。ここで\(n,m\)はグラフの頂点数と枝数です。既存の\((1-\epsilon)\)近似アルゴリズムで最速なものは\(O(mn^{1/2}\epsilon^{-1})\)で、それを更新しています。

グラフの各枝を抵抗とみて、\(s,t\)の間に一ボルトの電圧をかけた時に、どの枝を何アンペアの電流が流れるかという問題があります。これは線形連立方程式として表現でき、近似で良ければ効率的に(\(\widetilde{O}(n+m)\)時間で)解けることが知られています。このテクニックをサブルーチンとして用い、グラフを少しずつ変更しながら何度も、電流を計算することで、最大流を近似しています。何故それで上手くいくのかかなり不思議な気分になりました。

最大流業界では\(O(mn^{1/2})\)という計算量がバリアになっていたらしく、これを破ったのが評価されて、今回のSTOCのベストペーパーの一つに選ばれていました。

* Non-Uniform ACC Circuit Lower Bounds by Ryan Williams

CCCのベストペーパーです。この論文ではNEXPとACC0という二つｓの計算量に対して、\(NEXP \not \subseteq ACC^0\)を示しました。

NEXPは非決定性チューリングマシンである\(k \geq 0\)が存在して\(2^{n^k}\)時間で受理できる言語の集合です。\(ACC^0\)では\(AND/OR/Mod_6/NOT\)素子を使う回路で、素子の個数が入力長の多項式倍、深さが定数(入力から出力までに通る素子の数が定数個)のものを考えています。ある言語が\(ACC^0\)に入るとは、そのような回路で受理できることを言います。

おそらく\(P\)と\(NP\)という計算量は有名なので、それと比較して考えるのが良いでしょう。まず\(NEXP\)は\(NP\)よりもずっと強い(そうに見える)クラスです。\(NP\)は非決定性チューリングマシンで多項式時間で受理できる言語の集合ですが、\(NEXP\)では指数時間かけて良いからです。それに対して\(ACC^0\)は\(NC^1\)というクラスに含まれています。\(NC^1\)は、入力長の多項式個の計算機を用意すれば、\(O(\log n)\)時間で解くことが出来る言語の集合です。要するに並列計算が効率的に出来るということです。これは\(P\)よりもずっと弱い(そうに見える)クラスです。

それにも関わらず\(ACC^0\)は\(NEXP\)を含まないということすら示せないのが現状でした。基本的に二つの計算量の分離は、数十年進歩が無くても普通という、非常に難しい問題です。それを解決したので、ベストペーパーは文句なしというところでしょう。

著者のRyan WilliamsがFCRCでうけたインタビューがYou Tubeにアップロードされていますので、興味があれば聞いてみてください。

* 感想

FCRCは大きなイベントで面白いのですが、折角多くの会議が多数集まっている割には、それぞれ独立で互いの交流が無い印象を受けました。興味がある会議が有ったら自分で足を運べということなのでしょうが、もう少し異なる分野との交流の機会を増やす工夫があると良いかもしれません。

これは主にSTOCについての感想なのですが、各論文の内容が難しくなりすぎていて、講演を聞いていても良く分からないということが多々有ります。

STOCに通る論文というのは、基本的に抽象化された話題が多いです。例えば、既存の数ある結果を上手く一般化しました、などです。なので初心者がその貢献を理解するには、まず今まで何が知られていたかを知る必要があります。勿論、証明の詳細は追うのはもっと難しいです。

講演時間は20分なのですが、どうせ証明を理解するのは難しいので、20分のうち15分は既存の結果のサーベイに使うというルールが有ると大分聞きやすくなると思いました。

専門家にとっては退屈でしょうが、会議は色んな分野の人が集まる場所なので、他分野の人に自分の分野に興味を持ってもらうのには、それで丁度良いように思います。専門家向けの講演はワークショップなどでも出来るわけなので。

と、批判的なコメントを二つ書きましたが、勿論会議は総じて楽しかったです。自分と似た種類の人が大勢集まるということが普段はなかなか無く、ずっと研究の話をしていても嫌がられない環境はかなり良かったです。今後も継続的にFCRCやその他の会議に出席できるように頑張っていきたいと思います。