特定領域研究
「新世代の計算限界」 ニュースレター 第 3 号 2005/7/11
はじめに
このニュースレターは，特定領域・新世代の計算限界のメンバーの情報交換と交流を目的とした情報発信誌です．毎回，いくつかの研究関連の記事と，特定領域のスケジュール・活動報告と，各研究者の活動予定などをお送りいたします．今回は，東北大学徳山豪先生の経験談と，6月に行われた全体会議，幹事会の報告を行います．
１．「群れ派」の研究の仕方 − 徳山 豪 (東北大学)
２．第２回全体会議を振り返って − 浅野 哲夫 (JAIST)
３．2005年度第1回幹事会議事録 − 事務局
「群れ派」の研究の仕方 徳山 豪 (東北大学)
最近は「引きこもり」や「ネットが友達」など一人でいるのが居るのがいいという方も結構いるらしいが，私は典型的な「群れ派」である．特定研究のおかげでいろいろな人の考えが聞けて，おしゃべりが出来るのは楽しくて仕方が無い．そういう場では少々躁状態になるので，声がでかくて「うざったい」（特に岩間さんや西関先生と一緒だと）が，暖かくお許しいただけるとありがたい．大体が教授室に1時間とじっとしていられないで学生研究室をうろうろしているので，学生には（だれも口に出して言わないが）うっとうしい存在である．そんな性格なので，一人でコツコツ本や論文を読んで勉強するのは苦手で，常に人との関りが幸運をもたらしている．宇野さんのリクエストもあり，そんな話（記憶が薄れているので，意図せずフィクションが入ったらごめんなさい）をしてみる．
食事とドライブ
楽しいおしゃべりの相手というと，浅野哲夫先生（二人の取り決めにより，「浅野さん」と書く）がなんといっても第一である．1988年にはじめての海外出張でイリノイ大学でのACMのSCG（計算幾何学シンポジウム）に行ったのがお付き合いのはじまり．日本でもお会いしたことはあったのだが，当時私は純粋数学（代数的群論）から計算機科学に転向して1年経たないほどの新米で，大先生相手に気後れして直接お話をしたことがなかった．
イリノイ大学のあるアーバナ・シャンペーンというところは平らな大地以外に何にも無いところで，しかも会議参加者は見知らぬ人ばかり．大体が食事をする場所も近くにない．うろうろしていると，うしろから「こんにちは」の声がして，黒いサングラスを掛けたヒゲの先生がニコニコしている．「夕ご飯，どうします？ みんなと一緒に行きません？ 僕，レンタカーしてるから．」 うれしかったなあ．なんといっても人間は食べることが一番． おまけに，後でIBMのWatson研究所でホストをしてくれたAlok
Aggarwalや，研究での転換のきっかけをくれたMicha Sharirら有名人たくさんに紹介してもらった．結局会議期間中ずっと浅野さんの車に同乗したのだが，気に入ってもらえたらしく，「せっかくだから，一緒に研究しましょう．2次元のハッシュ問題だけど，興味ある？」 この研究は後で「トポロジカルウォーク」というアイデアを生み，私の出世作（1991SCG）になったのだが，浅野さんとの出会いが無ければ今の半分も研究人生が楽しくなかっただろうと思う．
話のついでだが，この会議で，「ちょっといいか」といって，話しかけてきた二十歳くらいのパデュー大学の中国人学生が居た．テーブルで無理やり向かい合わせたかと思うと，いきなり「計算幾何学の並列アルゴリズムに将来性はあると思うか，返答は如何に」と質問してくる．なんだなんだと思いながら適当に答えていると，「Thank you , 参考になった」といって握手してバイバイである．この生意気な学生はDanny Chen．当時はまだ論文も無い学生だったが，今ではトップクラスの研究者で，貴重な共同研究者である．
講演依頼は喜んで受けよう
STOC-FOCS-SODAとよく言うが，こういった会議に最初に論文を通すのが難しい．私の場合は，山下雅史先生と渡辺治先生のおかげである．といっても共同研究ではなく，駆け出しの研究者だった私に，「ランダムアルゴリズムについての一時間講演をお願い．絶対いい講演ができるから．」とおだてながら迫ったのがこのお二人（詳細は忘れたが，IEICE関係で，聴衆はずいぶんたくさん居た）． 当時ランダムアルゴリズムが世界的にブレイクし，反面日本ではあまり研究者が居なかったことは事実だが，ともかく自分でランダムアルゴリズムを設計したことが無い人間が「良い講演」をするのは難しいし，オリジナルな結果がまったく無いチュートリアルをするのは恥ずかしいと思った．講演期日までの間，柄にもなく一生懸命にさせられた結果が，割り当てや輸送問題を計算幾何学のランダムアルゴリズム手法で解く（問題自体は研究中だったが，ランダムというのは考えても居なかった）というもの．幸運なことにいい問題に当たった（1991SCG,1992SODA）が，講演を断っていたら運はめぐってこなかったろう．
人の話に首を突っ込むと
誰かが面白そうな（研究の）話をしているときに，話に加わりたいが邪魔をすると悪いなと思うかもしれない．IBMの東京基礎研究所で入社4年目くらいの頃，当時の上司の岩野さんと加藤直樹先生（これも加藤さんと呼ぶ）は頻繁に共同研究をしていた．ちょうど私の研究も軌道に乗って，翌年からアメリカ赴任という状況だったが，加藤さんが岩野さんを訪れて来た．ご挨拶でもしようと二人の話している会議室に（呼ばれもしないのに）行くと，なにやら面白げな話をしている．ぐずぐずしている間に，「徳山さんは専門家だから，聞いてよ」というのでありがたく参加すると，幾何学的な動的最小木とパラメトリックなマトロイドについての加藤さんの知識と発見の話題である． O(n^4) がマトロイドの理論で O(n^3) になるらしい．その場で考えてみると，計算幾何学のテクニックでも O(n^3) になるし，両方を組み合わせると O(n^2) にも出来るようである．わずか1時間ほどのDiscussionで出来た論文が，「動く点集合の最小木について」（1992FOCS）． さらに，関連するテーマで，たくさん（1995SODA,1999SODA,1999FOCS,2001SCG）論文を書いた．結論として，人の話には遠慮なく首を突っ込むべきである．
朝目覚めると
「ワーム食べませんか？」 玉木さんと最初に会ったときに彼が言った言葉である．1992のFOCSで，ワームホールラウティングの講演をした直後， 講演に使った（したがってOHP のガラスの上をのたくりまわった）グミキャンディーのミミズのおもちゃを半分にちぎって，片方を銜えながら．こんな面白い人がIBMの研究所にやってきて，2年間同室だったのだから，いい研究ができないわけがない．まず手始めにということで，Micha Sharirと学会のlunchで一緒したときに「解くべきなのだが，まったく手掛りがない」といわれて挑戦し続けていた「放物線のレベル問題」について玉木さんに話すと，Lovaszのマッチングとカバーリングの双対定理という道具を使って，あららといううちに解けてしまったのはおどろいた（1995SCG）．私一人では3年間うまくいかなかったのに． また或る時，国際会議で同室して，時差のせいで朝（？）3時に目覚めると，玉木さんなにやら思索にふけっている．「目が覚めましたか，ちょっと一緒に考えませんか？」．こちらは目覚めただけで起きたわけではないのだが，一緒につきあう．これで出来たのが1997年のISAACで最優秀論文賞をもらった研究（なんだか，私はサンチョ・パンザみたい）．
さて，玉木さんと私ではタイプはだいぶ違う．共通の趣味である囲碁を打つと良くわかるのだが，私は直感派で諦めが良く，玉木さんは論理（読み）を積み重ねないと納得しない．囲碁は個人ゲームだが，研究は協力して出来るので，違うタイプが重なると相乗効果で大変よろしい．考えてみると，「浅野−加藤−玉木−徳山」は4人ともタイプはそれぞれ違うように思う（どう違うかは，皆さんで判断してください）．浅野さんがリーダーシップを取って，この4人で合宿をしたりして，随分楽しく共同研究をしてきたものである．
研究のエピソードは書き出すと尽きないのだが，残りはまたの機会にしようと思う．
第２回全体会議を振り返って 浅野 哲夫 (JAIST)
去る６月１６日から２日間に亘って開催された第２回の全体会議について報告します．昨年，特定研究がスタートして以来，平成１６年１０月に東北大学で開かれた第１回の全体会議，今年の２月に京都で開かれた国際会議に引き続いての会合ですが，最初の２回についてはまだ成果を出せる状況にないということもあって，招待講演を主とする構成になっていました．代表幹事の伊藤先生から，東京電機大学の築地先生と一緒に次回の全体会議を計画するように言われたとき，どのようなコンセプトにするか色々と考えました．まず考えたことは，特定研究にとって最も重要なことは何かでした．とにかく偉大な成果を出すことが要求されている訳ですが，特定研究としての成果というのは，単独では難しかった問題を特定研究のグループの力を借りて初めて解くことに成功したというものであることが望ましい訳です．つまり，うまくコラボレーションができたかどうかが問われる訳です．もちろん，理論のことですから，何度も集まったから必ず成果が出るという保証は何もありませんが，社会に対しては，少なくともコラボレーションがうまく行くように最大限の努力はしたということが見えなければならないと考えた訳です．では，そのためにはどうすればいいかですが，コラボレーションを成功させるためには，まず我々のグループの中でどんな成果があるのか，誰がどんな研究を行っているのかを知ることが肝腎です．ということで，まずは全ての研究班に自分たちの研究を紹介してもらおうという考えに至りました．もちろん，全員に話をしてもらうのが最適ですが，そうすると時間が２日では全く足りないので，ポスターの形式にしました．コラボレーションの切っ掛けは，日常会話に近い，ちょっとした会話の中から生まれるものだと個人的に信じているので（とにかく，興味ある共通の話題がないことにはやる気が起きないので），とにかくインフォーマルな会話の時間を大切にしたかったのです．
もう一つの視点は，私がこのコミュニティーが好きなのは，日本の社会にしては珍しく年齢の壁が高くないことです．理論をやっていると，どうしても若い人の集中力には負けるから，経験が豊富だというだけで威張ることができません．これが年齢を余り感じることなく誰とでも話せる雰囲気を醸し出しているのだと思います．いつの間にか自分も年寄りの部類に入ってしまっているのでしょうが，気分はまだ20代です（言い過ぎです，ごめんなさい）．この雰囲気を大事にしたくて，偉い人にだけ講演をお願いするというスタイルを取りませんでした．
最後に，４人の方にだけ普段より長めの時間を用意して講演をしてもらいました．いずれも活躍が伝わってくる講演で，改めて本グループの質の高さを実感しました．今回の４人の講演者は私の一存で決めましたが，４人のご講演を聞いただけでも本グループの全体像が浮かび上がる，うまい人選になっていたのではないかと自画自賛しています．もちろん，講演を快諾して頂いた４人の講師の講演の質の高さが成功に導いたことは言うまでもありませんが．次回はどんな趣向で全体会議が企画されるか今から楽しみです．
2005年度第1回幹事会議事録 事務局
日時：2005.6.16 12:00--13:50
場所：国立情報学研究所１２階会議室
[報告事項]
○ 教科書シリーズの進行状況 (杉原，山下，室田，渡辺)
（仮題）アルゴリズムサイエンスシリーズ 全16巻 A5版 約200ページ
○ 電子ジャーナル (徳山)
・ECCCの成功（ドイツの大学）を見習ってECCCのアルゴリズム版を作る？
・維持が大変（お金と人手）
・本屋を巻き込めば継続可能だが
-> 全体討論で議論
○ 成果報告書 (堀山)
・印刷体のものを各研究代表者に送る
○ 確率シンポジウム (徳山)
・資金は基本的に折半
○ ニューズレター (宇野・牧野)
・７月出版を目安に準備
[検討事項]
○NHC国際会議に続いて，今年度も国際会議を開催するか？
・若手の育成を重視し，サマースクール（またはスプリングスクール）を実施
・前半スクール後半チュートリアル？
-> 全体討論で議論
○次回の全体会議の場所，担当者
・名古屋大，平田先生
・１１／２１，２２予定
○林先生のコメント
・審査が厳しくなっている．
- きちんと評価ー＞反映 という傾向．
- 中間審査の結果で減額されたり，最終報告の結果で次期プロジェクトに
反映されたりするようになってくる．
・この特定は情報基盤を支える重要なものである．
・現実的な解法，具体的な成果が求められる．
・領域の連携が重要：単なる集まりでは無い（連携することでどんな結果が得られたか？
目標に対してどこまで到達したか？）
・「情報学」が終わるのでこの特定が情報系の代表格になる
・グランドチャレンジを期待する．
特定領域研究も２年目に入り，段々と盛り上がってきて事務局も嬉しい忙しさです．春学校，ミニプロジェクトなど新しい試みも始まります．皆様，これからもご協力の程よろしくお願いします．
★ 報告書の作成について皆様のご協力有難うございました．作成方法やフォーマットなどについてご意見をお持ちでしたら，伊藤，堀山までお寄せ下さい．
★ ミニ研究集会はどなたがどんな思いつきで企画されても結構ですから，どしどし行って下さい．総括班から費用のサポートもいたします．
全体会議 （予定） 11/21(月),22(火) 名古屋大学
列挙合宿 (宇野毅明・中野眞一・上原隆平)
3日間，泊り込みで列挙・数え上げを中心に組み合わせアルゴリズムに関する雑談をします．
9/27(火)13:00 - 29(木)11:30 群馬県伊香保町 群馬大学セミナーハウス
7/11(月)-15(金) ICALP,
ポルトガル・リスボン
7/11(月)-15(金) IFORS, ハワイ (参加者: 伊藤大雄, 巳波)
7/18(月)-21(木) ランダムネスと計算に関わるワークショップ 仙台国際センター (参加者: 元木光雄)
7/19(火)-22(金) Combinatorial Pattern Matching 韓国済州島
7/25(月)-27(水) LAシンポジウム 福岡県宗像市
8/15(月)-17(水) WADS, カナダ・ウォータールー
8/16(火)-29(金) COCOON, 中国・昆明
8/29(月)-9/2(金) MFCS, ポーランド・グダニスス
10/1(土)-5(水) CP2005 スペイン・バルセロナ (参加者: 元木光雄)
10/3(月)-6(木) ESA, スペイン・イビザ
10/21(金)-10/22(土) 第１７回RAMPシンポジウム 青森県弘前市 シティ弘前ホテル
10/23(日)-25(火) FOCS 2005 アメリカ・ピッツバーグ
12/7(水)-12/9(金) I-SPAN2005 アメリカ・ラスベガス
12/19(月)-21(水) ISAAC, 中国・海南島
1/22(日)-1/24(火) SODA2006 アメリカ・マイアミ
ニュースレター各号は電子メールで配布する予定です．短い記事や連絡事項は全て掲載しますが，長い記事，イベントの詳細などはwebページに掲載する予定です．webページには詳細まで全てを載せた完全版を掲載して，目次，あるいは各記事の末尾のURLを参照すると，web版の同じ記事を参照できるようにいたします．
記事は，各回，１つの研究課題に担当をお願いする予定です．各研究課題で2000-4000字程度，研究に関わる記事を書いていただければと思います．通常，このようなニュースレターでは，研究成果を報告するのが一般的だと思われますが，この特定領域では「研究者の交流」に焦点を当てたいため，「研究の成果以外」の記事を面白く解説していただければと思います．例えば，最近参加した国際会議の情報を，どのようなものが流行っていたか，何が面白かったか，などの主観的な解説を交えて報告したり，最近考えている問題，あるいはオープン問題を，この辺までは解けるがここがうまくいかない，といった解説を交えて紹介する，という形です．
また，研究者間の交流を促進するため，各研究者の，国内外の会議への出席予定を集約して掲載していこうと考えています．研究者の交流には，顔をあわせる回数を増やすことが肝要です．他の研究者の参加予定がわかれば，会議への出席のモチベーションを高めることにもつながり，それがディスカッションや研究成果を生むきっかけにもなるでしょう．特定領域メンバーの皆さんには，自分のわかる範囲で，国内外の会議・研究会の情報と，自分の参加予定を教えていただければと思います．
この他，個人からの寄稿を募集いたします．100-1000字程度で，情報宣伝されたいことを自由な形式で書いて送っていただければ，掲載いたします．メールで配布する関係上，テキスト形式のものしか扱えませんが，そこはご了解お願いいたします．
次回は10月ごろを予定しています．
★ ニュースレター編集委員では，皆様からのご意見をお待ちしております．編集方針や内容の追加など編集全体にかかわることから細かいことまで，幅広いご意見をお願いいたします．
■■ 新世代の計算限界 ニュースレター ■■
編集委員長 宇野 毅明 uno@nii.jp (問合せ先)
副編集委員長 牧野 和久 makino@sflab.sys.es.osaka-u.ac.jp