China Theory Week

Tag

# 理論計算機科学

Yuichi Yoshida

Engineer

吉田です．

先日デンマークのオーフスという街で開催されたChina Theory Week 2011というイベントに参加してきましたので，その報告をします．China Theory Weekは中国の清華大学とデンマークのオーフス大学が主催するイベントで，理論計算機科学の世界で成果を上げている学生を集め，講演をしてもらい，互いの交流を深めあおうという趣旨のイベントです．僭越ながら僕も招待されたので参加してきました．下の写真は会場に置かれていた看板なのですが，誰か”仙オ”の意味を教えてください…

基本的に午前は基調講演と学生による講演，昼ごはん後，午後も学生による講演が続きます．これが月曜日から金曜日まで丸一週間続きます．これだけでもなかなかハードと言えますが，火曜日と木曜日には夜7時頃からピザ＆ビールセッションという，ビザとビールを頂きながら，皆が未解決問題を持ち寄って紹介するというイベントが有りました．ビールはなかなか美味しかった．それ以外の日も結局，誰かと一緒に晩ご飯を食べながら研究の話をしたり雑談をしたりしているので，毎日ホテルに帰るのは夜の11時ぐらいになっていて，寝て起きたらもう次の日の講演が始まるという濃密さでした．

招待されている人もなかなか豪華で各分野の濃い話を聞くことが出来ました．清華大学とオーフス大が主催者ということで，その二つの大学の関係者が少し多かったですが，それ以外は本当に世界中から人を集めていました．基調講演の中で幾つか印象に残ったものを記しておきます．

Algorithms for Circuits and Circuits for Algorithms by Ryan Williams

Ryan Williamsは(non-uniform) ACC0 != NEXPという計算量に関する数十年来の未解決問題を最近解決した人です．ACC0はある形をした回路で計算できる問題の集合を表す計算量のクラスです．NEXP (nondeterministic exponential time)は，皆さんご存知のNP (nondeterministic polynomial time)をさらに広くしたクラスです．この講演はACC0 != NEXPという問題の歴史，証明の概要，今後の課題についてでした．面白いのはACC0 != NEXPを証明するのに，ACC0に関する問題の上限を利用して，ACC0がNEXPを表現できないという下限を示していることです．具体的には「与えられたACC0の回路の出力を1にするような入力はあるか」という問題を，自明な\(2^n\)という計算量から少しだけ改善しています．

Exponential time algorithms by Thore Husfeldt

指数時間アルゴリズムに対する最近の結果についての講演でした．NP完全な問題は多項式時間で解くことは不可能と思われているので，指数時間\(c^n\)で解くしか有りません．けれども兎に角速く解きたいので，その\(c\)を出来るだけ小さくしようという研究が盛んです．例えば3SATは自明な方法で解くと\(2^n\)時間かかりますが，知られている一番速い方法は\(1.308^n\)時間です．この講演で扱った話題は以下のようなものでした．

包除原理を用いた指数時間アルゴリズムの紹介．特にグラフの彩色数を\(2^n\)時間で求めるアルゴリズム．
指数時間予想(3SATは\(2^{o(n)}\)時間では解けないという予想．\(o(n)\)は\(n\)より真に小さい関数を表す)とSparsification Lemmaを組み合わせて，様々な問題が指数未満の時間では解けないことを示す．
グラフ中の2点\(s,t\)と更に\(k\)点が与えられて，\(k\)点を通る\(s\)から\(t\)へのパスを求める\(\exp(k) \mathrm{poly}(n)\)時間アルゴリズム

僕が思うに2000年代になってから，指数時間アルゴリズムの研究が特に盛んになってきた気がします．指数時間アルゴリズムは，極度に数学的なわけではなく，数学的でないということは得られるアルゴリズムも実用的にちゃんと速くなっており，プログラミングコンテストの雰囲気を感じるので，個人的には嫌いではありません．

Position-based cryptography by Harry Buhrman

量子暗号の話です．思いきり話を簡単にすると，「線分上にいる人の場所を，両端の基地局から電波を流すことで推定する問題」を暗号化して安全にしようという話です．もし人が正直であれば，電波を受け取った瞬間にその電波をそのまま送り返すことで，両端の基地局は送り返された電波の時間差を利用して，人の場所を推定することが出来ます．けれども，悪意のある人が途中で電波を受け取って，適当なタイミングで電波を返すと，基地局は間違った場所に人がいると推測してしまうかもしれません．このようなことが出来ないような仕組みを作ることは出来るか，というのがテーマでした．基本的に古典ではこれは不可能という結論なのですが，量子もつれを使うと出来るようになるようです．

余り僕は量子計算に興味が無いので，量子に関しては素人なのですが，それでも講演はとても分かりやすかったです．量子の業界ではこういった問題を考えているのかということを学べたのが収穫でした．

学生の発表の分野も多岐にわたって，そういう分野や問題が有るのかと教えられるものばかりでした．普段，国際会議とかですと，興味が余りない発表は飛ばしてしまうのですが，今回のように参加人数が少なくて参加者と顔を合わせざるを得ないという状況だと，話も真剣に聞くというものです．例えば今回は，算術回路が恒等零かどうかを決定的に検査する，指数時間アルゴリズム，ネットワークコーディング，シンプレックス法の(或るpivotルールにおける)計算時間の下限，劣モジュラ関数最大化といったトピックについて学ぶことが出来ました．

また，交流を深めるのも大事ということで色々と話かけてきました．例えば3SATに対する指数時間アルゴリズムの世界記録(\(1.308^n\))を持つTimon Hertliが来ていたのですが，この問題は僕の所属する研究室でも活発に研究されていたというのもあって良く話をしました．またCMUの学生のYuan Zhouとは一緒に論文を書いていながら一度も会ったことが無かったので，この機会にということで仲良くなってきました．以下は一緒に遊びに行った旧市街(という名前のテーマパーク)と鹿園の写真です．