特定領域研究
「新世代の計算限界」 ニュースレター 第 5 号 2006/8/17
はじめに
このニュースレターは，特定領域・新世代の計算限界のメンバーの情報交換と交流を目的とした情報発信誌です．毎回，いくつかの研究関連の記事と，特定領域のスケジュール・活動報告と，各研究者の活動予定などをお送りいたします．今回は，名古屋大学高木直史先生の研究科紹介と，11月に行われた全体会議，幹事会の報告を行います．
１．ドイツの長期滞在体験 − 高木 剛 (公立はこだて未来大学)
２．18年度第１回全体会議を振り返って − 山下 雅史（九州大学）
３．2006年度第1回全体会議討論会 − 事務局
ドイツの長期滞在体験 高木 剛 (公立はこだて未来大学)
特定領域「新世代の計算限界」に参加の方で、海外留学の経験のある方ももあると思います。私はドイツへの1年間留学の後、当時所属していたNTTの欧州研究所に3年間派遣され、そのあとダルムシュタット工科大の助教授となり、2005年までドイツに計8年間滞在するという経験を持ちました。この体験の中から、Dagstuhlセミナーとドイツの助教授システムについて少し書きたいと思います。
皆さんの中には、ドイツのDagstuhlで開催されたセミナーに参加された方もおられると思います。招待公演を中心したClosed Workshop形式で議論が進められ、情報科学の分野で先導的なアイデアを生み出してきたセミナーとして知られています。このDagstuhlセミナーの成功は、世界のトップレベルの研究者を集めている点が第一に上げられます。優秀な研究者を集めるにはセミナー主催者の努力が大切ですが、Dagstuhlには一度行くと忘れられない古城を改築した優雅な建築、充実した図書館や宿泊室などの施設面の優位性もあると思います。ダルムシュタット工科大学の同僚から聞いた話ですが、Dagstuhlセミナーの設立は、ドイツにおける情報科学のパイオニアとして知られるGuenter Hotz教授が80年代にドイツの情報科学を成功に導こうと模索していた際、Dagstuhlで散歩の途中に古い城を見かけ、これを改良して情報科学セミナーの拠点にしようと思い立ったのが切掛けとのことです。Guenter Hotz教授は、1969年にドイツの大学初となる情報科学部をSaarbruecken大学に開設、同年にドイツ情報科学学会(Gesellschaftfuer Informatik)を設立、1974年には第2回のICALPをSaarbrueckenにて開催するなど、ドイツにおける1970年代の情報科学の発展に大きく貢献しました。更に1990年には、上記のDagstuhlセミナーの他に、Saarbrueckenにマックスプランク情報科学研究所(Max Planck Institut fuer Informatik)の開設も手がけるなど活発な活動をしてきました。
話は変わりますが、ドイツでも大学改革が進められており、改革の目玉として助教授のポストが2002年に新設されました。私はこの助教授制度の第一号としてダルムシュタット工科大学で教鞭をとる機会に恵まれました。ドイツで大学教授を目指す研究者は博士号を取った後さらに十分な研究実績を上げ、大学教授資格(Habilitation)を取る必要があるため、若くして独自の研究費を持つことができる米国の大学教授職に人気を奪われ、大学研究の空洞化が進んでいました。このような状況を踏まえ、博士号を取得して間もない若手研究者(35歳以下)に教授並みの資格を与える助教授制度をドイツ政府主導でスタートしました。この助教授には、教授会への参加、研究費の申請、博士論文の主査、秘書の補助など、教授と同様の権利が与えられ、同時に、最低週6時間の講義、修士および博士論文の指導、研究室の予算管理、学部/大学院運営など、教授と同等の義務も持ちます。助教授が通常の教授と一点異なるのは最大6年の任期制であることです。講義などの教育面、論文数などの研究面、研究費の取得状況などで総合的に評価され、終身在職権のオプション(Tenure Track)を与えるようにも規定されています。実際にダルムシュタット工科大学で助教授になった感想としては、他の教授達からFacultyメンバの一人として同等な扱いを受け、助教授だからといった差別はなかったです。また、助教授に就任した後は、本特定領域研究のようなドイツ政府科研費の研究プロジェクトに参加する機会も得られました。私も含めて助教授の多くが数年後に他大学から終身在職権を得ており、任期制の弊害も少ない様子でした。
ドイツでの体験に関しては、滞在が長期に及んだこともあり話題が尽きません。また機会があれば別の話も報告したいと思います
18年度第１回全体会議を振り返って 山下 雅史 (九州大学)
去る6月21日から6月22日にかけて九州大学ベンチャービジネスラボラトリーで本年度第１回の全体会議が開催されました。実は、私は両日ともに他の仕事が入っていて、五月雨式にしか出席することができませんでした。講演をして頂く方を相談したときには、この先生の話を聴きたいと我儘を言っていたのですが、当日は結局ほとんど出席できず、御講演をして頂いた先生には本当に失礼を致しました。自信を持って全体会議を振り返ることはできないのですが、有意義な会議をお過ごし頂けたとすれば幸いです。
このような理由もあって、プログラムや会場のお世話は--このような理由の有無に関わらずいつも通り--定兼先生と小野先生に完全にお任せしてしまいました。そして、いつも通り、無事に会議を終えることができました。定兼先生と小野先生、ありがとうございました。
私は、今までにいくつかの重点領域／特定領域研究に参加させて頂きました。いずれも班の活動を中心に据えていて、例えば、分子プログラミングでも、２つの理論班が合同でミーティングを行っています。今回の全体会議を企画するときにも、従来に関わった領域研究の全体会議のように班毎の会議を持つ必要があるのではないかと思ったのですが、より動的に新しいグループの育成を目指す未解決問題セッションを優先するという、浅野先生、平田先生と受け継がれてきた方針に新鮮さを感じました。
折角の機会ですから、私からも最近興味を持っている問題と未解決問題を提供してこの報告を終ることにします。私の最近の興味の一つは「有限グラフ上の乱歩の設計」です。有限グラフGが与えられたときに、良い性質を持つ乱歩を設計することが目標です。即ち、良い確率推移行列を計算することが目標です。分っている主な内容を列挙します。
1) 任意のグラフGに対してカバー時間(およびヒッティング時間)O(n^2)を実現する確率推移行列Mが簡単に計算できる。
2) パスグラフPは任意の確率推移行列Mに対してヒッティング時間(およびカバー時間)はOmega(n^2)である。
3) 任意のグラフGに対してヒッティング時間O(n^2)を実現する確率推移行列を以下の意味で局所的な情報から構成できる：M(u,v)はuおよびuの隣接頂点の次数情報だけから決まる。
4) 任意のグラフGに対してカバー時間O(n^2 log n)を実現する確率推移行列を以下の意味で局所的な情報から構成できる：M(u,v)はuおよびuの隣接頂点の次数情報だけから決まる。
未解決で残されている問題は、1)と4)のカバー時間に関するギャップを埋めるために必要な局所情報の量です。uおよびuの隣接頂点の次数情報だけでカバー時間O(n^2)を達成できると予想しています。
全体討論 (2006.6.22) 議事録 記録：堀山貴史
[ 活動報告 ]
○前回の全体会議以降の研究集会
・春学校 (2/27 〜 3/3) [浅野 先生, 西野 先生]
・COMP-NHC 学生シンポジウム
電子情報通信学会 総合大会 (3/26, 国士舘大学) [山下 先生]
・ミニ研究集会
- 暗号 (2/16, はこだて未来大学)
- ジオメトリ (3/15 〜 17, 京都)
・回路とシステム軽井沢ワークショップ 招待講演セッション (4/24, 軽井沢)
○ポスドク： 玉置 卓, 山本 真基 (４月〜, 勤務地 京大)
○事務員： 川嶋 知子 (５月〜)
○平成17年度 成果報告書 [堀山]
発行, 冊子体を研究代表者と幹事の先生方に発送済み
■ 進行状況報告 / 討論 ■
○教科書シリーズ [杉原 先生, 山下 先生]
「入口からの超入門」(浅野哲夫)、「出口からの超入門」(岩間一雄) が10月頃に刊行の予定。「複雑性の階層」(荻原光徳) が年明けに、続いて３ヶ月毎に刊行の予定。脱稿から出版までに半年ぐらいかかるので、著者の方は早めに原稿の作成をお願いします。
○ニュースレター [牧野 先生, 宇野 先生]
年数回の発行態勢。次回は７月頃を予定。
編集委員の引継ぎ … 天野先生、宮野先生
○電子情報通信学会 特集号
・和文論文誌Ａ (６月) [増山 先生]
・英文論文誌Ｄ (８月) [和田 先生]
○電子ジャーナル [定兼 先生]
・プレプリントのサーバを立ち上げた。ECCC のようなものを目指す。
・特定領域のメンバーの論文を載せ、外部に宣伝をする。
○研究集会の企画
・アルゴリズムと計算理論に関する日韓合同ワークショップ
(7/4-5, 北海道大学) [柳浦 先生]
特定領域が主催、SIGTCS(韓国), COMP研, アルゴリズム研が協力
・iETA 2006, ICALPのサテライト ワークショップ (7/16, イタリア) [渡辺 先生]
資料を 150 部ぐらい作る。iETA 以外に、11月の全体会議等でも配布する。
・秋学校 (11/15 〜 17, 瀬戸市) [平田 先生]
合宿形式のスクール (３日間), 講師１人 ４〜５時間 (２時間講義
+ ディスカッション)
講師 (予定)
- Thomas Erlebach (UK)
- Uri Zwick (Tel Aviv)
- Tibor Szabo (ETH)
- Magnus M. Halldorsson (Iceland)
- George Ausiello
+α ？
・第２回 COMP-NHC 学生シンポジウム [渡辺 先生]
今年３月の IEICE 総合大会での学生シンポジウムが好評だったので、第２回を、来年３月に企画している。
・日本OR学会 数理計画シンポジウム (10/12-13, 京大)
・ミニ研究集会, 自由に企画してください。
・次回の全体会議
- 11/18 (土) 名古屋大学
- 朝１人講演してもらう + 全体会議 (講演でなく討論)
- 特定領域としての成果を見据える必要がある
(岩間先生の成果 briefing 30分 + 外部の方を招待して御意見をいただく)
・briefing のための資料
- いい conference, journal
- Non expert の人にも分かる成果 (世間にアピールする成果)
(自薦他薦を問わず, この研究をここに発表したらというのもあり)
- 受賞 等 (指導学生の受賞も含む)
○特定領域「情報爆発」との連携 [岩間 先生]
「情報爆発」の状況：３つのどれかで頑張る
- 国際的学術性 (top conference, journal で戦える成果)
- 応用・社会性 (世の中の人々に有用性を理解して頂ける成果)
- システム、ツール的価値
(論文にはなりづらくとも研究者仲間に有用性を享受してもらえる成果)
・総括班会議 … 特定領域の内部から数人、外部の人が注文
○今後の活動計画
・国際会議のサポート
2007年4月 Hungary-Japan、7月 JCDCG、12月 ISAAC、関連 Workshop [徳山 先生]
・特定領域の成果発表会, 公開シンポジウム [定兼 先生]
時期 … 最終年度 年明け、 開催 … 東京、 外部の人を招待
○次の特定領域に向けて
・少人数のコミッティを作って、検討を進める
委員候補：今井先生、加藤先生、徳山先生、山下先生、渡辺先生 (50音順)
・この特定領域の特色は？
社会へのアピール
- non-expert アカデミックでない人向け
- アカデミックの人(物理、化学、数学、工学)の先生に納得していただけるもの
■ 列挙合宿 (世話人：宇野、中野) ■
3日間、泊り込みで列挙アルゴリズムに関する雑談をします。
9/28(木)13:30 - 30(土)11:30 群馬県伊香保町 群馬大学セミナーハウス
旅費の補助も可能です。お問い合わせください。
8/22(火)-24(木) IFIP/TCS 2006 Santiago, Chile
9/11(月) 日本OR学会第56回シンポジウム (愛知大学 車道校舎)
9/11(月)-15(金) ALGO 2006 チューリッヒ (スイス)
9/18(月)-20(水) DISC2006 Stockholm, Sweden
9/22(金) OR学会中部支部シンポジウム「離散システムの理論と社会システムの設計」
10/12(木)-13(金) RAMP2006 京都大学時計台百周年記念ホール
10/22(日)-24(火) FOCS2006 Berkeley, CA, USA
12/15(金)-17(日) WINE 2006 Patra, (Greece)
12/18(月)-20(水) ISAAC2006 インド カルカッタ
1/7(日)-9(火) SODA07 New Orleans, Louisiana, U.S.A
7/9(月)-13(金) EURO XXII Prague, Czech
ニュースレター各号は電子メールで配布する予定です．短い記事や連絡事項は全て掲載しますが，長い記事，イベントの詳細などはwebページに掲載する予定です．webページには詳細まで全てを載せた完全版を掲載して，目次，あるいは各記事の末尾のURLを参照すると，web版の同じ記事を参照できるようにいたします．
記事は，各回，１つの研究課題に担当をお願いする予定です．各研究課題で2000-4000字程度，研究に関わる記事を書いていただければと思います．通常，このようなニュースレターでは，研究成果を報告するのが一般的だと思われますが，この特定領域では「研究者の交流」に焦点を当てたいため，「研究の成果以外」の記事を面白く解説していただければと思います．例えば，最近参加した国際会議の情報を，どのようなものが流行っていたか，何が面白かったか，などの主観的な解説を交えて報告したり，最近考えている問題，あるいはオープン問題を，この辺までは解けるがここがうまくいかない，といった解説を交えて紹介する，という形です．
また，研究者間の交流を促進するため，各研究者の，国内外の会議への出席予定を集約して掲載していこうと考えています．研究者の交流には，顔をあわせる回数を増やすことが肝要です．他の研究者の参加予定がわかれば，会議への出席のモチベーションを高めることにもつながり，それがディスカッションや研究成果を生むきっかけにもなるでしょう．特定領域メンバーの皆さんには，自分のわかる範囲で，国内外の会議・研究会の情報と，自分の参加予定を教えていただければと思います．
この他，個人からの寄稿を募集いたします．100-1000字程度で，情報宣伝されたいことを自由な形式で書いて送っていただければ，掲載いたします．メールで配布する関係上，テキスト形式のものしか扱えませんが，そこはご了解お願いいたします．
次号は11月ごろを予定しています．
★ ニュースレター編集委員では，皆様からのご意見をお待ちしております．編集方針や内容の追加など編集全体にかかわることから細かいことまで，幅広いご意見をお願いいたします．
■■ 新世代の計算限界 ニュースレター ■■
編集委員長 宇野 毅明 uno@nii.jp (問合せ先)
副編集委員長 牧野 和久 makino@sflab.sys.es.osaka-u.ac.jp