2010-08-28
[ツッコミを入れる]
| 個人サイト |
| Preferred Infrastructure |
今日はSupercon 2010の結果発表を観に行ってきました。前年まではTAをしていたのですが、今年は直前にアメリカにいて、直後にスペインに行くので、一日だけの参加に留めました。上記のページには殆どまだ何も情報が無いのですが、関東の高校が一位〜三位を占めるという結果でした。
今回は問題がなかなか面白かったです。今までだと最適化問題が主流で焼きなまし＋適切なスコア関数以外やることあるんかいなという状況だったのですが、今年は正確な解を求めないといけない言わばICPCタイプの問題でした。具体的には50*50の盤面にいくつか障害物が置いてあり、障害物を避けながら2*1のタイルを敷き詰める置き方は何通り有るかという問題です。20*100とかならDPで、8*10^8とかでも行列乗算で解けるんでしょうか。コンテスト的にはそれに適当にヒューリスティックスを入れて、大部分の入力に対して解が求まれば勝てるようです。
ただジャッジが全データに対して正解データを用意しているということは50*50でも解く方法があるということなのですが、僕は最初全く分かりませんでした。二部グラフの完全マッチングの数え上げってPRASみたいなのは有ったような気がするけど#P-completeじゃなかったっけと悩んでいました。後で教えてもらったところによると、グリッドは二部グラフじゃなくて平面グラフとみなすのが良いようです。そして何と、平面グラフの完全マッチングの数え上げは多項式時間で解けるらしいです。リンク先の資料がとても詳しいです。Pfaffian Orientationというのが肝だそうで。
このアルゴリズムを僕は今まで全く知らなかったので、試しに実装してみました。例えば以下のような入力に対しては(各インスタンスの最初の行は、問題番号、高さ、幅、Mod)、
1 3 2 100000次のように出力します。最初にPfaffian Orientationを出力したのち、タイルの敷き詰め方の総数を出力しています。解が大きい時は桁落ちします。
..
..
..
1 3 2 100000
..
..
.*
1 3 6 100000
......
......
......
1 3 7 100000
....***
.......
.......
1 10 10 100000
****..****
***....***
**......**
*........*
..........
..........
*........*
**......**
***....***
****..****
.>.
v v
.<.
v v
.>.
3
.>.
v v
.<.
v
. *
0
.>.>.>.>.>.
v v v v v v
.<.<.<.<.<.
v v v v v v
.>.>.>.>.>.
41
.>.>.>. * * *
v v v v
.<.<.<.>.>.>.
v v v v v v v
.>.>.>.<.<.<.
41
* * * * .>. * * * *
v v
* * * .<.<.>. * * *
^ v v v
* * .<.<.>.<.>. * *
v ^ v v v v
* .<.<.<.<.>.<.>. *
^ v ^ v v v v v
.<.<.<.<.>.<.>.<.>.
v ^ v ^ v v v v v v
.<.<.<.<.<.>.<.>.<.
^ v ^ v v v v v
* .<.<.<.>.<.>.<. *
v ^ v v v v
* * .<.<.<.>.<. * *
^ v v v
* * * .<.>.<. * * *
v v
* * * *
32768
先に結論を書いておきますと、8/23からの週(末)が暇なので、関西で何かイベントが有ったり、会ってくれる人が居れば連絡ください！
去年の10月からお世話になっていたRutgers Universityですが、この8/19に日本に帰国します。おかげ様でゆっくり研究することが出来ました。その間サポートして下さった方々に感謝です。大学の人も家の人もみんな親切で本当に助かりました。出来れば日本とアメリカとその日の気分で住むところを選びたいところですが、そうもいかないですね…。
アメリカに来てから考え始めて論文にするところまで持って行けたのが多分五本(うち一つは参考にしていた論文に致命的なミスが有ってポシャりましたが)で、今やっているプロジェクトが三つほど有るので、抜群に仕事をしたかというと微妙かもしれませんがまぁ及第点かなと思っています。こちらの大学の人とやっているプロジェクトはうち一つだけで、本当はもっと一緒にやりたかったのですが、思っていたより量子コンピュータを研究している人ばかりだったので仕方がないと言ったところでしょうか。勿論研究とは関係なしに友人は沢山出来ました。
留学したものの義務としてそのメリットを語る必要があるのかなと思ったので少し考えていました。理論計算機科学というのは基本的には「計算機に纏わる数学的に綺麗な事柄を証明していく」というのが目的で、現段階で一番大きな目標が「P != NPを示す」ということなのだと思います。当然これは一人でやるわけではなくて、世界中の人たちで協力しあってやっていく。その時に彼らがどんな人達か知ることはとても重要だと思うのです。一緒に仕事をするのも彼らだし、何が重要か(言い換えれば綺麗か)を判断するのも彼らです。基本的に理論計算機科学はアメリカを中心に動いているので、その本場で彼らがどのような流儀で仕事をしているのかを直に見れるのは良い経験であったなぁと思います。勿論そんな堅苦しいことを考えずに、単に外国の文化に触れるのはそれ自体楽しいことです。
逆にデメリットは余り思いつきません。日本の友人とは日本に帰ればまた会えますし、食べ物は確かに油っこくて辛い時がありますが、言ってもその程度です。
なので留学をするチャンスがある人には積極的に勧めたいです。ずっと一箇所に長い間いると空気が淀んで思考も固まってくるので、たまにはそこを離れて換気をするのが良いと思います。そういう意味では僕もコンピュータから離れて別のことしろって話ですね…。
P != NPを示すのに代数幾何が使えるという話があるのですが（Lance Fortnowによる動画解説）、本格的に学ぶべきかどうか悩む…。Ketan Mulmuleyによる講義の資料とビデオが有るので、勉強する材料は揃っているのですが、代数幾何はちょっと余りにハードルが高い。けれども近く発展して行くのは目に見えている。今出川通りの北に転がっている人たちをこっちに引き込んだ方がいい気がするなぁ。代数幾何自体を発展させようとして苦労している人たち沢山いそうだし。
まだ先の話ですが6/14からPseudorandomness in Mathematical Structures Programというワークショップに参加する予定です。お題はpseudorandomness(擬似乱数)です。擬似乱数の直接的な応用は暗号だったり、確率を用いたアルゴリズムを使わないように変形する(BPP = Pが目標)ことだったりだと思うのですが、実のところ僕はその辺りの話は興味がありません。それより僕が面白いと思っているのは、pseudorandomnessを他の分野の証明の道具に使うことです。例えば関数f : {-1,1}^n → {-1,1}のフーリエ展開が良い例です。フーリエ展開はある関数を別の特性関数の線形和で表すことと言って良いと思います。この時、どんな関数も「(nに寄らない)定数個の特性関数の線形和」と「ノイズ」に分けれるというのがフーリエ展開から示唆されます。このノイズの部分を良くpseudorandomと読んでいるのですが、ノイズの部分を捨ててしまえば、元の関数fは、要するに定数個の特性関数でよく近似出来るというわけです。個人的にはこの部分がとても哲学的な示唆に飛んでいて好きです。詳しくはFOCS 2007のTerrence Taoによるチュートリアルを参照してください。
この性質を使うことで、実に様々な定理が証明されています。まず、上のフーリエ関数はCSPの近似困難性の解析をする上でよく使われています。また、上の考えをグラフに適用すればSzemeredi's regularity lemmaも証明できます。そこから性質検査の話にもつながります。他にもTao & Greenの「素数列中には任意の長さの等差数列が存在する」という定理の証明の道具にもなっています。
話を元に戻すと、このワークショップでその辺りの道具の今の状況が知れれば良いな思っています。また最近、軽く群論の検査にも手を出しているのですが、群論とpsudorandomの関係もこのワークショップで語られるそうなので、それも楽しみです。
今年もPFIでは夏季インターンを開催します。
内容は前年度のインターンの方々の感想を見てもらうのが一番早いかと思います。面接対策にはなるんではないでしょうか(笑)(追記) ところでオフィスが新しくなりました。写真
こんな情報をここに書いても世の中の２，３人にしか影響が無い気がするのですが、最近Unique Games Conjecture (UGC)周りの発展の勢いが凄いです。暫く用語の説明が入るので詳しい人は読み飛ばして下さい。
まずUnique Gamesのインスタンスは(U, V, E, [R], Π)で与えらます。(U, V, E)は二部グラフ、[R]は大きさRのラベル集合、π_e∈Πは枝eに付随するラベル間の置換です。目的はUとVにラベルを与えて、π_eを満たす枝の個数を最大化するというもの。UGCとは「任意のεに対して、あるRが存在して、ラベル数RのUnique Gamesが与えられた時、その最適解が1-ε以上かε以下かを区別するのはNP-Hard」というものです。UGCは現在の理論計算機科学の中心的なトピックの一つと言えると思います。
何故このUGCが重要かを述べるには、まず近似アルゴリズムの話をしなければ成りません。最大カットや最小頂点被覆問題はNP-hardなことで有名な問題です。つまり最適解を求めるのは殆ど無謀です。なのでそれは諦めて、例えば最大カットなら正確な最大カットの何割の大きさのカットなら多項式時間で求めることが出来るだろうか、というのが問題になるわけです。現在知られていることを結果だけ述べると、最大カットは最適解の0.878倍のカット、最小頂点被覆は最適解の2倍の頂点被覆を多項式時間で見つけることが出来ます。
ではこれらを0.878+εや2-εで近似するのはNP-Hardなのかというのが次に解くべき問題になります。実のところ…これは分かっていません。現在知られているのは、最大カットだと0.941以上、最小頂点被覆だと1.36以下はNP-Hardというものです。UGCが発明されたのは、どう頑張っても埋めれないこのギャップを埋める為です。実際この予想を仮定すると0.878や2という値がタイトということが示せるのです。
UGCが考え出されたのは2002年なのですが、それから凄い勢いで研究がなされて、今では任意のCSP(最大カットを含む)に対して、UGCを仮定した上で「この近似度までは線形時間で求めることができるが、それよりちょっとでも良くしようとするとNP-Hard」ということまで分かってきました。
ここまでが導入です。アメリカの東海岸にいるといい大学が周りに沢山あるので、新しい結果の発表が頻繁になされます。その中でインパクトが有ったものを二つ概要だけ紹介します。一つ目はOn the Optimality of a Class of LP-based Algorithms by Kumar, Manokaran, Tulsiani, and Vishnoiです。これは上に述べた「CSPに対する近似アルゴリズムと、UGCを仮定した上でのタイトな近似困難性」と同様な結果を最小頂点被覆を含む広いクラスで証明したものです。最大カットは任意の頂点集合の分割が解になっているのですが、最小頂点被覆はそうではなくて、全ての制約を満たさないと解として認められないのが難しいところです。
僕のいるRutgers大でVishnoiによる講演が有ったのですが、元々1時間のはずの講演が延長を許されて2時間になった上に、世話人(Mario Szegedy)の授業でも話の続きが許されるという面白いことになっていました。興味が有ったのは世話人と数人の生徒だけで、他の生徒は聞かずに帰ってしまったようですが。
二つ目は、Subexponential Algorithms for Unique Games and Related Problems by Arora, Barak, and Steurerで、UGCは2^O(n^poly(ε))時間で解けると述べています。これが面白いのは、UGCはεをo(1)(例えば1/log log n)にするとNP-Hardではなさそうと予想出来ることです。というのもNP-Hardな問題を解くには必ず指数必要という予想が別にあるからです。これのお陰でUGCでεをo(1)にすることで解決(?)を見ていた問題(Sparsest Cutなど)が、全然解決になっていなかったということが分かりました。おそらく今後数年でそういった問題に対する準指数時間アルゴリズムが与えられて行くのでしょう。
この辺りの証明技法はとても面白いので、自分の研究分野に上手く取り込もうと画策している最中です。
先週は僕の部屋にAram Harrowという人が来ていて結構楽しかったのですが、残念ながら彼は量子の人なので特に研究に発展することはなし。
ニュージャージーも随分日中は暖かくなってきました。まだ風は少し冷たいですが、コートはもういらなさそうです。アメリカ人は強靭でもうランニングシャツに短パンとかになってます。凄い。
ところで日本に帰ったら環境が激変してみんな並列プログラミングでもしているのではないかと危惧したので、最近は暇な時間に以下の二冊を読んでいます。
Purely Functional Data Structuresは、結局のところ永続データ構造(Persistent Data Structure)が内容の殆どを占めます。永続データ構造はデータ構造の一種で、データの内容を更新したあとも、昔のデータ構造を操作することが出来るという代物です。実現方法は幾つかあって、ログを真面目に取るか、更新される部分だけ新しい領域に作って元のデータと共有出来るところを共有するかというのが代表的な方法でしょうか。何故これが並列プログラミングと関係があるかというと、永続データ構造は更新が基本的に無いのでスレッドセーフにするのが容易だからです。所々感心するところは有りましたが、万人が読まなければならない本というわけでもないかなと思いました。永続データ構造はその性質上、普通のデータ構造と比べて計算量が悪くなるのですが、それをどうやって避けるかというのが此の本の主旨で、永続データ構造があるからこそ、こんな非自明なことが出来るという例が無かったのが、そう思わせる原因かもしれません。例えば非自明なこととして、永続データ構造を使うとRange Reportingという問題が自然に(そこそこ)高速に解けるという話があります。これは秋葉君が思いついて聞いた話なのですが、僕はこのアイデアにいたく感動したので、こういった話が散りばめられていれば、もっと人に薦められたかもしれません。ちなみにRange Reportingへの応用は既知らしくて、例えば講義資料(ppt)にもなっています。
二冊目のThe Art of Multiprocessor Programmingはこれは楽しい！理論と実践のバランスがとても良く取れていて、並列プログラミングの理論を作ってきた人たちの思考を辿るのも楽しいし、実際にコードを書くときに役に立つ知識も沢山載っています。例えば何故CPUの演算にcmpxchg(compare and swap)が選ばれているかがこれを読めば明確に理解出来ます。こんなの誰も教えてくれなかった…。並列なコードは会社の同僚が普段から書いているのですが、僕はどうも自信が無かったので、これで少しは追いつけたらなと思っています。後は経験だろうなぁ。主にデバッグの。
_ okamoto7 [どうもお久しぶりです．ご意見ありがとうございます．「解が多いときに桁落ちする」ということはたぶん本質的で，それを克服..]
_ oxy [お久しぶりです。今年も面白い問題をありがとうございました。 高校生に求めるのは酷ですが、ICPCの参加者でC/C+..]
_ okamoto7 [正しいかどうか，という判断は私にできないのですが，中国人剰余定理を使う方針は実践上よさそうですね．]