特定領域研究
「新世代の計算限界」 ニュースレター 第 7 号 2007/5/22
はじめに
このニュースレターは，特定領域・新世代の計算限界のメンバーの情報交換と交流を目的とした情報発信誌です．毎回，いくつかの研究関連の記事と，特定領域のスケジュール・活動報告と，各研究者の活動予定などをお送りいたします．今回は，東京工業大学の伊東先生による共同研究に関するエピソードの紹介と，5月に行われた全体会議の報告を行います．
１．共同研究を通じたタコツボからの脱出 － 伊東 利哉 (東工大)
２．2007年度第1回全体会議議事録 － 事務局
共同研究を通じたタコツボからの脱出 伊東 利哉 (東工大)
この度，ニュースレター編集委員長の宇野毅明さん(国立情報学研究所)より，ニュースレターの記事の執筆依頼をいただき，あっさり了解はしたものの，いざ記事を書くとなると，何を書いたら良いものやら意外に筆が進まない．もともとの宇野さんのご依頼では，
なるべく「研究成果」ではなく「研究にまつわる成果以外の話」を書いていただいて，成果の情報を交換するのみにとどまらず，もっと人的な部分での理解と交流を図りたい
とのことでしたので，それならと最近の共同研究において，自らの未熟さを痛感した経験を「共同研究を通じたタコツボからの脱出」と題して紹介させていただきたいと思う．
著者は，数年前から「最小値独立置換族の構成」の研究に取り組んできたが，昨年「近似的k限定最小値独立置換族のサイズの下界」を導出し，その結果をECCCのTR06-017として公表した．この結果は，
(1) 一様分布でサンプルされる近似的k限定最小値独立置換族Fからある正方行列Vを定義する
(2) その行列の階数をラムゼー数を用いて評価し，一様分布でサンプルされる近似的k限定最小値独立置換族Fのサイズの既存の下界を改善する
というものであり，取り敢えずプライオリティーは確保したのでどこかのジャーナルにきちんと投稿しようとのんびり構えていた．その後，2006年7月29日にある人からメールが届いた．メーラの送信者の表示にはNoga
Alonと書いてありきっと，国際会議のCFPのメールだろうと思いつつ本文を開いてみると，予想通り「あの」Tel
Aviv大学の
Noga Alon氏であった．しかし，メールの内容は国際会議のCFPなどではなく，著者のアプローチの(2)の部分でラムゼー数を用いないで，Alon氏の以前の結果を用いて評価すれば，最終的な結果が
(3) 任意の分布でサンプルされる近似的k限定最小値独立置換族Fのサイズの下界をさらに改善することが可能
であることを伝えるものであった．さらに，そのメールにおいては，もし著者(伊東自身)が拒否しないならば，著者のアプローチとAlon氏のアイディアを取り入れた共著論文を書きましょうという内容も含まれていた．著者自身，ECCCでの結果を任意の分布でサンプルされる場合に拡張しようと試みてはいたものの，ラムゼー数を用いる限り壁が突破できずにいた．正にタコツボ状態だった訳だが，Alon氏のアイディアを取り入れて，一般の分布でサンプルされる場への拡張が成功した．そのやり取りの時系列(日本時間表示)は
7月29日 20:10 Alon氏から論文マージの打診メール
7月31日 15:35 伊東から承諾の回答
7月31日 17:05 Alon氏からマージ作業方針のメール
7月31日 19:54 伊東からLaTeXファイルをAlon氏にメール
7月31日 22:55 Alon氏からマージ作業承諾のメール
8月 1日 1:51 Alon氏からマージされたLaTeXファイルを受信
8月 1日 13:41 伊東の修正とコメントをAlon氏に連絡
8月 1日 18:29 Alon氏から伊東の修正に関する回答メール
8月 1日 20:09 伊東からAlon氏に最終版確定のメール
8月 1日 20:25 Alon氏より最終版合意のメール
8月 1日 20:30 伊東よりRandom Structures and Algorithmsに投稿
というもので，短時間で投稿原稿の準備が完了した．因みに，Alon氏のメール(2006年7月29日 20:10着信)から，著者の返信メール(2006年7月31日 15:35送信)までに2日が経過しているのは，最近著者自身が恒常的に大量のメールの処理にうんざりしているため，週末は殆どメールを見ないためである(2006年7月29日は土曜日で7月31日は月曜日である)．この論文は，若干の修正の後，最近めでたく採録された．
正直，Alon氏とのやり取りはかなりエキサイティングだった．まずは著者のアクションに対するAlon氏からの返事が早いので，こっちもノロノロできない．また，投稿原稿の準備段階での，著者からのコメント・質問にも実に真摯に回答をくれることが印象的だった．
さらに，直近の「共同研究を通じたタコツボからの脱出」の事例を紹介しよう．今年になってある東工大内部の会議で渡辺治氏と一緒になり，会議後に「最近Weighted Random Popular Matchingの研究をしていて」と雑談したことが，そもそもの始まりであった．乱択を広めよう運動を進める乱択オタク(失礼)の渡辺氏が，この問題に関心を寄せて下さり，毎週土曜日の午後に議論を開始した．まずは，著者が関連研究のサーベイ結果を説明し，その後著者の結果の概要を披露した．渡辺氏からはいろいろと貴重なコメントをいただき，著者の証明の欠陥などを発見するきっかけとなった．そして，Weighted Random Popular Matchingに関するある閾値の上界と下界の導出までは辿りついたが，残念ながら，その上界と下界には大きな隔たりがあった．下界の導出には，複数の事象の和集合の確率の下界を評価する必要があり，著者はこれを包除原理を用いて導出していたため，上界との隔たりを埋めることに手を焼いていた(実際には，計算機実験などの結果から，上界の改善ではなく，下界の改善の可能性が見込まれていた)．この際も，正にタコツボ状態に陥っていた．これに対して，渡辺氏からChebyshevの不等式を利用して，目標の下界が導出可能であることのコメントをいただいた．著者のアプローチで行った諸々の計算などはほぼそのままChebyshevの不等式による評価でも生かされ結果は上界とほぼ一致する下界の導出に成功した．この結果は，6月のCOMP件＠北海道大学で
Toshiya Itoh and Osamu Watanabe, Weighted Random Popular Matching (重み付き乱択最適選好マッチング)
というタイトルで発表予定である．
最後になって恐縮だが，本記事において，普段から「タコツボ」に陥りがちな著者を，この2つの共同研究を通じて見事に救い出してくれたお二人に感謝の気持ちを捧げたい．本当にありがとう！
全体討論（2007.05.15）議事録
日時: 2007.05.15 14:00～16:10
場所: 東大工学部６号館会議室
[ 活動報告 ]
○秋学校
○iETA
○信学会総合大会学生シンポジウム：
○軽井沢ワークショップ招待講演セッション
○ミニシンポジウム「新世代計算限界と地球環境問題」（12/5-6 東大）
○ミニ研究集会
・Complexity（12/1 東工大; 12/28 電通大）
・暗号理論（3/2 電通大）
・組合せゲーム・パスル（3/16, 豊橋技科大）
・列挙アルゴリズム（3/27-29 群馬大）
○「アルゴリズム・サイエンス・シリーズ」（共立出版）
○電子情報通信学会誌和文論文誌A特集号(2006年6月刊行)
○電子情報通信学会誌英文論文誌D特集号(2006年8月刊行)
○ポスドク: 玉置卓（2006月4月～ 京大）, 山本真基（2006月4月～ 京大）
○招聘研究者（2006年度に15名）
○事務補佐員: 川嶋知子（2006年5月～）
[ 進行状況報告 ]
○HERCMA2007のミニシンポジウム：浅野哲
○ISAAC2007：徳山
○KyotoCGGT2007：加藤
○AQIS 2007：岩間
○ALT&DS2007：瀧本
○ニュースレター：宇野: 今年度１回目を近日中に発行予定
○2006年度報告書：堀山: 印刷中、６月配付予定。ウェブ版はすでに掲載。
○電子ジャーナル：定兼: デモが行われた。試用しつつ改善していく。エディタ団を決める。
○ミニプロジェクト
・ジオメトリ：加藤
・列挙：宇野
・ゲーム：伊藤
・Complexity：垂井
・地球環境問題：杉原
[ 検討事項 ]
○秋学校: 本年度も実施するか検討され、開催の方向でまとまった。担当者については、北陸先端大の浅野哲夫先生が候補に上がった。次期：１０月か１１月？場所：白山セミナーハウス？（要送迎バス）
○次回の全体会議の時期、場所、担当者 ISAAC2007(12/17--19)の直前の土曜日(12/15)の東北大が有力候補としてあがった。（日曜日(12/16)は西関先生の還暦記念のイベントあり。）
○報告書の締切り: 予算の関係で2008年1月末原稿締切り、年度中に印刷完了とする。
○終了翌年度のシンポジウム: 特定領域研究終了翌年度（つまり2008年度）に成果報告のシンポジウムを行うために、300万円上限で予算を申請することができるので、申請することとする。
○「計算理論による情報価値の創造」について、徳山教授より説明があり、議論した。
全体会議
（予定） ISAAC2007(12/17--19)の直前の土曜日(12/15)の東北大が有力候補
6/6(水)-8(金) SoCG'07 Gyeongju 韓国
6/6(水)-9(土) WEA2007 ローマ
6/8(金)-16(土) FCRC 2007(含む STOC2007) San Diego, California
6/11(月)-15(金) KyotoCGGT2007 京大
7/9(月)-13(金) EURO XXII Prague, Czech
7/9(月)-13(金) ICALP 2007 Wroclaw, Poland
8/1(水)-5(日) FAW 2007, LanZhou, China
9/3(月)-6(木) AQIS2007, 京大 芝蘭会館
9/5(水)-7(金) FIT2007, 中京大学 豊田キャンパス
9/20(木)-22(土) HERCMA 2007, アテネ(ギリシャ)
10/1(月)-4(木) ALT2007, Sendai International Center (仙台)
10/1(月)-4(木) DS2007, Sendai International Center (仙台)
10/8(月)-12(金) ALGO 2007, Eilat (Israel) この中でESA 2007が開催されます
10/20(土)-23(火) FOCS 2007, Providence, Rhode Iland, (USA)
12/17(月)-19(水) ISAAC2007, 仙台
ニュースレター各号は電子メールで配布する予定です．短い記事や連絡事項は全て掲載しますが，長い記事，イベントの詳細などはwebページに掲載する予定です．webページには詳細まで全てを載せた完全版を掲載して，目次，あるいは各記事の末尾のURLを参照すると，web版の同じ記事を参照できるようにいたします．
記事は，各回，１つの研究課題に担当をお願いする予定です．各研究課題で2000-4000字程度，研究に関わる記事を書いていただければと思います．通常，このようなニュースレターでは，研究成果を報告するのが一般的だと思われますが，この特定領域では「研究者の交流」に焦点を当てたいため，「研究の成果以外」の記事を面白く解説していただければと思います．例えば，最近参加した国際会議の情報を，どのようなものが流行っていたか，何が面白かったか，などの主観的な解説を交えて報告したり，最近考えている問題，あるいはオープン問題を，この辺までは解けるがここがうまくいかない，といった解説を交えて紹介する，という形です．
また，研究者間の交流を促進するため，各研究者の，国内外の会議への出席予定を集約して掲載していこうと考えています．研究者の交流には，顔をあわせる回数を増やすことが肝要です．他の研究者の参加予定がわかれば，会議への出席のモチベーションを高めることにもつながり，それがディスカッションや研究成果を生むきっかけにもなるでしょう．特定領域メンバーの皆さんには，自分のわかる範囲で，国内外の会議・研究会の情報と，自分の参加予定を教えていただければと思います．
この他，個人からの寄稿を募集いたします．100-1000字程度で，情報宣伝されたいことを自由な形式で書いて送っていただければ，掲載いたします．メールで配布する関係上，テキスト形式のものしか扱えませんが，そこはご了解お願いいたします．
次号は10月ごろを予定しています．
★ ニュースレター編集委員では，皆様からのご意見をお待ちしております．編集方針や内容の追加など編集全体にかかわることから細かいことまで，幅広いご意見をお願いいたします．
■■ 新世代の計算限界 ニュースレター ■■
編集委員長 宇野 毅明 uno@nii.jp (問合せ先)
副編集委員長 牧野 和久 makino@sflab.sys.es.osaka-u.ac.jp