RANDOM+APPROX 2007

ボストン滞在２週間の後には RANDOM+APPROX 2007 に参加するため，プリンストン大学へ移動しました．

今後プリンストンに行くこともあろうかという同業の方々のためにいくらか情報を書いておきます．プリンストンには空港がなく，最寄の空港はニューヨークシティのニューアーク空港のようです．そこから New Jersey Transit (NJ Transit) という列車に揺られること約１時間でプリンストンに到着です．ニューアーク空港から NJ Transit の駅へ行くのは少し分かりづらいのですが，ターミナル間を繋いでいるモノレールの一番端の駅で乗り換えられます．一方，プリンストン駅はプリンストン大学のキャンパスそばにあることもあり，大学へのアクセスはかなり楽かと思います．

今回の出張では Nassau Inn というホテルに泊まりましたが，実はプリンストン大学周辺にはホテルがほとんどありません．レンタカーなどを利用しない限り，このホテルがほぼ唯一の選択肢になるかと思います．建物は古く宿泊費も結構張りますが，このホテルからだと大学まで本当に歩いてすぐです．NJ Transit の駅からも歩いて15分程度なので交通のアクセスという点では最良でしょう．ホテルの設備にはあまり期待しない方が良いです．インターネット接続はありますが，部屋やビジネスセンターから繋ぐと有料でかなり高いです．（確か30分で７〜８ドル程度だったと思います．）ただ，なぜかフロント前のロビーには無料の無線LANがあったので，いつもそこでメールチェックなどをやってました．このホテルのすぐそばに Nassau st. という大通りがあり，その周辺にはレストランなどがたくさんあるので食べる場所には特に困らないと思います．

私が滞在していたときは（たまたまかとは思うのですが）ほぼ一週間毎日雨が降り続き，８月なのにメチャクチャ寒く，日中でも20℃を切っていたと思います．手持ちの衣類に長そでシャツが一着だけあったのですが，それを着ていても肌寒いぐらいでした．結局寒さに耐えきれず，大学の売店で厚手長そでのパーカーを購入して愛用してました．

さて肝心の会議ですが，会議の名前通り計算におけるランダム性と離散最適化問題の近似アルゴリズムに関する論文が大部分を占めています．ただアルゴリズムよりも計算量理論的な色彩が強いです．例えば近似アルゴリズムに関して言えば，具体的な問題に対する近似アルゴリズムの提示よりも，近似困難性に関する議論が多かった気がします．
講演も3日間毎日朝9時〜夕方6時までみっちり詰まっていて結構ハードでした．

一番面白かったのは，Rocco Servedio の招待講演でした．内容は学習理論の結果が property testing や近似アルゴリズムなどに応用できるよ，という話だったのですが，彼がやっていた half space の学習の応用などは今考えている線形符号の復号問題や格子問題にも使えそうです．