2008年度 今井研究室紹介 ２００8年4月7日

今井研究室の研究テーマ 『アルゴリズム』の研究 今井研究室の研究テーマは情報科学の基礎である「アルゴリズム」そのものである。

今井研究室の研究テーマ 未踏域への挑戦 現実社会への応用 しかし今井研では理論に留まることなく、 アルゴリズムの研究により、未踏域への挑戦、現実社会への応用を目指している。

今井研究室の研究テーマ 量子 現実社会での応用 未踏域への挑戦 生体認証 ゲーム探索 暗号理論 計算幾何 グラフ理論 離散・連続最適化 未踏域とは将来の科学である量子の分野を、 現実社会への応用では交通流解析やネットワーク、ゲノム解析などへのアルゴリズムの応用に 今井研では挑戦してきました。 離散・連続最適化 計算代数 組合せ論 計算量理論

博士論文(1) 計算幾何 アレンジメント再構成の組合せ論的複雑度評価（青木 保一，1993） リーマン計算幾何：凸包，ボロノイ図とデローネ型三角形分割 （大西 建輔，1998） 特徴多様体上のクラスタリング問題について（稲葉 真理，1999） 整数計画法による三角形分割の最適化（田島 玲，2000） 三角形分割の組合せ論（竹内 史比古，2001） 多面体的複体のシェリング向き付け： シェラビリティー判定と離散最適化の組合せ構造 （森山 園子，2006） 有向マトロイドの実現を与える方法および特徴のある有向マトロイド （中山 裕貴，2007） 量子計算・量子暗号 計算量的観点における量子計算モデルの計算能力（小林 弘忠，2002） 資源制約下における量子計算モデルの計算能力（ルガル フランソワ，2006） エンタングルメントコストの解析とホレボ容量の計算（下野 寿之，2006） Bell不等式とカット多面体：量子情報科学と組合せ最適化の結合 （伊藤 剛，2007） 現実世界の設定下で定量的な安全性を初めて保証したデコイ法量子鍵配送の理論と実験（長谷川 淳，2008） 量子状態上のボロノイ図とその量子通信路容量の数値的評価への応用 （加藤 公一，2008） 今井研がどのような研究をしてきたところか知ってもらう 5

博士論文(2) 計算代数 単模およびLawrence型整数計画問題に対する計算代数的解析 （石関 隆幸，2003） ゲームツリー探索 AND/OR木探索アルゴリズムDf-pnの提案とその応用（長井 歩，2002） ゲノム・文字列処理 文書検索と圧縮の統合-接尾辞ソート、ブロックソート法、接尾辞配列- （定兼 邦彦，2000） 部分文字列の性質に基づく計算機援用大規模生物実験設計 （土井 晃一郎，2001） 生物配列情報の比較と検索のための高速なアルゴリズムの研究 （渋谷 哲朗，2002） グラフ理論 Tutte多項式の計算アルゴリズムとその応用（関根 京子，1997） リンクベースのWeb上情報発見手法の新しいフレームワーク （浅野 泰仁，2003） ネットワーク ネットワーク通信において通信品質を保証するアルゴリズム （古賀 久志，2002） 6

最近三年間の修士論文 計算幾何 最小包含球問題から得られるCube グラフの向きづけ（西鳥羽 二郎，2007） Angular Voronoi Diagram の退化（牟田 秀俊，2008） 計算代数 代数幾何学的な多変数多項式の既約証明アルゴリズム及び周辺の問題 （ベック 和穂 エリック，2006） 計算量理論 Ｌ対Ｐ問題の折り返し対アクセス問題への関連付けとそれらの組み合わせ構造 （上野 賢哉，2007） 量子計算・量子情報 可解群に対する多項式時間量子アルゴリズム（乾 義文，2007） 二分NAND式木上の量子ウォークアルゴリズムの解析（鈴木 真吾，2008） 2-Prover 1-Round Game としてのベル不等式における最大量子破れ（高橋 敏明，2008） 交通流解析 車両軌跡データの分析による交通情報の把握とその応用（柴田 輝之，2006） 暗号理論 Final Round 攻撃対策のなされたAES に対するキャッシュタイミング攻撃（永岡 悟，2008）

研究室の活動 セミナー 週１回持ち回りで研究内容を発表 輪講 決まったテーマで論文、本を読む

研究室内に留まらない活動 今井研の活動は内部に留まらない 外部との交流も積極的に 外部の研究施設 共同研究 カナダ McGill大学の David Avis 教授 スイス ETH大学の Komei Fukuda 教授 国際会議、研究会 論文誌への投稿 外部の研究施設 ERATO-SORST 日経BPムック 「変革する大学 東京大学理学部」 より

研究室環境 研究室 311号室、314号室（図書室の隣） 個人用端末、机 PCを購入予定 計算サーバ プリンタ(カラー2台)とコピー機 図書館前 311号室

独りよがりでいいわけではない 研究を独力で行うために 外の世界と交流する 発表を行う能力を身につける 今井研の方針 研究について自分で考えること 独りよがりでいいわけではない 研究を独力で行うために 研究の流行盛衰を把握し良いテーマを設定する 外の世界と交流する 研究会に参加したり 世界の大学の人と共著を書いたり 発表を行う能力を身につける 自分の研究成果を知ってもらうために 今井研の目指す演習Ⅲの目標とは研究について自分で考えることを見につけてもらうことである。 研究のための基礎訓練として文献を探す、調べる テーマを自力で見つける能力 独りよがりなテーマでは意味がない！ 何を研究すればよいのか？なぜその研究が必要になるかを理解するセンスを見につけてもらうことが目標である。 もちろん質問は歓迎、メールを送るか研究室に来てもらえれば研究室の先輩が応対してくれます 今井研セミナーへの見学も歓迎しています 11

離散数学分野 松本宜丈（Ｍ２） 宮田洋行（Ｍ２）

離散数学分野の研究対象 離散構造 グラフ マトロイド 単体的複体 有向マトロイド 最適化 列挙アルゴリズム 最小包含球問題のCubeグラフ 向き付け可能性判定 Webリンクグラフの解析 単体的複体 有向マトロイド シェラビリティー 実現可能性問題 活用 貢献 最適化 線形計画法 半正定値 計画法 多項式計画法

最近の研究（１） マトロイドの列挙 マトロイドの列挙の目的： マトロイド理論研究のためのマトロイドのデータベースを作成する！ 過去の研究 要素数8以下のマトロイドの列挙 [Blackburn, Crapo, Higgs, 1973] 要素数12以下，ランク3のマトロイドの列挙 [Betten, Betten, 1999] 要素数9以下のマトロイドの列挙 [Meyhew, Royle, 2007] 30年以上 継続している研究 我々の結果 要素数10ランク4のマトロイドの列挙 [Matsumoto, Moriyama, Imai, 2007] 問題の難しさ： 同型なマトロイドを重複して列挙しないようにするにはどうするか 逆探索適用のために 新たなデータ構造を定義 逆探索：列挙アルゴリズム構築のための 一般的なスキーム [Avis, Fukuda, 1995]

最近の研究（２） 有向マトロイドの実現可能性判定 1112112123 2233233444 3444555555 0++++++0-- oriented matroid ??? realization abstraction 有向マトロイド 実行列 組合せ幾何と深い関係 有向マトロイドは 擬直線配置と関係 Grassmann-Plücker relations を半正定値計画問題として緩和 直線にできない （Pappusの定理） 線形計画より強力！ 要素数8，ランク4の有向マトロイドで 440個の実現不可能性を判定

演習IIIのテーマ例 グラフ 有向マトロイド その他，希望があれば幅広く受け入れます 不変多項式 有向マトロイド計画法 Tutte多項式，彩色多項式，ネットワーク信頼度など 有向マトロイド 有向マトロイド計画法 線形計画法の最小添字規則と深い関連 その他，希望があれば幅広く受け入れます

ゲーム理論 今井研究室 M1　奥田諒介

ゲームとは 複数の行動主体が自分のとる行動を選択し、その選択が互いに影響を及ぼしあう こっちが協力したのに 裏切られたらイヤだ こっちも裏切った方が 良いのかも・・・ 協力？ 裏切り？ A B 例：囚人のジレンマモデル 自分にとって出来るだけいい結果を導きたい 相手の選択も考慮に入れながら 自分にもっとも有利な選択をする 自分の行動だけでなく、 他のプレイヤーの選択も結果に影響する ゲーム理論の目的： 様々なゲームのモデルにおいて、プレイヤーが取るべき行動を考察する その結果ゲームの状態がどのようになるか予測する

ゲーム理論の応用範囲 幅広い応用範囲を持つ！ 経済学 社会学 政治学 論理学 ゲーム理論 生物学 情報科学 心理学 オペレーションズ・ リサーチ 幅広い応用範囲を持つ！

ゲーム理論とネットワーク インターネットの挙動をゲーム理論的に解析 交通工学 ： 情報科学 ： 市街地の渋滞モデル ネットワークの混雑モデル 市街地の交通量管理を ゲームとしてモデル化 ネットワーク上の通信の管理を ゲームとしてモデル化 Tam, Lam, 2000 Nhat, Obaid, Poirier, 2005 など など 異なる分野の研究を、自分の扱う分野に引き込んで用いることが出来る

その他、「自分はこう進めたい！」など歓迎します 演習３では・・・ １．自分の興味がある(計算機科学的な)問題を決めて、 ゲーム理論的に記述、定式化する　 プレイヤー、戦略はどのように書ける？ そのゲームの望ましい状態は何か？ ２．考えたゲームについて色々研究してみる 　 プレイヤーの戦略はどのようなものが良い？ ゲームの結果はどのようなものになるか？ ３．ゲームをプログラムで実装して、実験的に検証する その他、「自分はこう進めたい！」など歓迎します

情報科学演習３ 量子計算、量子暗号 徳田優(M2),長谷川淳(助教)

不確定性原理に基づく情報理論的に安全な暗号 なぜに量子なのか！？ Motivation 量子の特性を活かして、現代の計算モデルや暗号 プロトコルでは達成できていない、新しいアルゴリズム や暗号プロトコルを構築したい。 　　　　　　　　　　　 量子並列性を用いた高速アルゴリズムの実現!! 量子計算 　　　　　　　　　　　　　不確定性原理に基づく情報理論的に安全な暗号 量子暗号

量子計算 ある重要な問題クラスの問題において古典のアルゴリズムよりも高速に計算が可能！！ Shorのアルゴリズム ex) 素因数分解 古典の計算機では準指数時間 (´･ω･｀)しょぼーん。 Shorのアルゴリズム 量子計算では多項式時間で計算可能！！ (｀・ω・´)ｼｬｷｰﾝ Groverの探索アルゴリズム 古典のアルゴリズムでは の探索問題が、 量子計算では で実行可能！！

量子計算機の到来により現在の暗号システムは安全でない！！ 量子暗号 古典の暗号として代表的なRSA暗号などは素因数分解や離散対数問題などの 計算の困難に安全性が基づいている。(計算量理論的安全性。) つまり・・・ 量子計算機の到来により現在の暗号システムは安全でない！！ BB84プロトコル 不確定性原理に基づく情報理論的安全性 (無限の計算能力をもってしても破られない！！) secure

HSP 隠れ部分群問題 Non-Abelian HSP 量子計算 量子暗号 Shortest Vector Graph Isomorphism HSP Non-Abelian HSP グラフ同型問題に 安全性が基づく暗号 理論の構築 Non-Abelian HSPを 解くアルゴリズムの開発

今井研の量子研究 量子計算 量子情報 関連する他の分野 領域に制限の付いた量子計算量 隠れ部分群問題を解く量子アルゴリズム 計算量 計算幾何 最短ベクトル発見アルゴリズム ノイズの下での量子計算の理論，数値解析 グラフの量子彩色数 群論 グラフ理論 量子暗号の性能評価 量子誤り訂正符号の構築，性能評価 符号理論 量子情報 Bell不等式の列挙，破れの発見 情報幾何 量子情報幾何 量子通信路容量・量子エントロピー 情報理論

演習３の課題 量子を選択される方へ 予備知識はいりません。(基礎的な事項から学んでいただきますのでご安心を。) 量子に関することならば、いかなる分野でも対応していきたいです。 演習3の進め方(徳田案) 何はともあれ 論文を購読して発表してもらいます。 (英語、英語、英語・・・・と大変でしょうが、残念ながら卒論も英語なので。) 最終週辺りで余力があればプロジェクトを自分で決めて簡単に研究してみましょう。 (せっかく今井研の演習３にきてもらうので。もしかしたら卒論のテーマになるかも？) 皆さんの積極的な希望や質問を期待しております。 Appendix : 今井研の宣伝(徳田の独断) 部屋が綺麗になった！！　先輩方が親切だ！！　突発的な飲み会が多い！！ 学年の垣根がなく仲が良い！！　なにより先生が情熱的で素敵だ！！ (もう今井研にくる以外の選択肢はないですね。)