2006年度 今井研研究室紹介 ２００６年６月３０日

アルゴリズムの世界 今井研究室の研究テーマ 現実社会への応用 未踏域への挑戦 ゲーム理論 交通流解析 量子 ゲームツリー サーチ 計算幾何 実際今井研で研究してきたアルゴリズムはこのようにして 量子計算には計算量理論や計算代数、計算幾何を用いてブレイクスルーを起こし、 また現実社会では計算幾何を用いた交通流解析、 グラフ理論を用いたネットワークの問題解決に貢献してきた。 計算幾何 ネットワーク 計算代数 グラフ理論 組合せ論 暗号理論 離散・連続最適化 メタヒューリスティックス 計算量理論

博士論文(1) 計算幾何 アレンジメント再構成の組合せ論的複雑度評価（青木 保一） 特徴多様体上のクラスタリング問題について（稲葉 真理） リーマン計算幾何：凸包，ボロノイ図とデローネ型三角形分割 （大西 建輔） 整数計画法による三角形分割の最適化（田島 玲） 三角形分割の組合せ論（竹内 史比古） 多面体的複体のシェリング向き付け： シェラビリティー判定と離散最適化の組合せ構造 （森山園子） 計算代数 単模およびLawrence型整数計画問題に対する計算代数的解析 （石関 隆幸） 量子計算量 計算量的観点における量子計算モデルの計算能力（小林 弘忠） 資源制約下における量子計算モデルの計算能力（ルガル フランソワ） エンタングルメントコストの解析とホレボ容量の計算（下野 寿之） 組合せゲーム理論 AND/OR木探索アルゴリズムDf-pnの提案とその応用（長井 歩）

博士論文(2) ゲノム・文字列処理 部分文字列の性質に基づく計算機援用大規模生物実験設計 （土井 晃一郎） 文書検索と圧縮の統合-接尾辞ソート、ブロックソート法、接尾辞配列- （定兼 邦彦） 生物配列情報の比較と検索のための高速なアルゴリズムの研究 （渋谷 哲朗） グラフ理論 Tutte多項式の計算アルゴリズムとその応用（関根 京子） リンクベースのWeb上情報発見手法の新しいフレームワーク （浅野 泰仁） ネットワーク ネットワーク通信において通信品質を保証するアルゴリズム（古賀久志）

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

セミナー 輪講 FOCS,STOCセミナー 研究室の活動 週１回持ち回りで研究内容を発表 決まったテーマで論文、本を読む 中大と合同で最新の論文を読む

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

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

卒論で何をするか まずテーマを決める 既存の研究を調べる 研究の流れを掴む 自分のやりたいことは？ それは”研究”になるものか？ 演習３を通じてなにか得たものがあったはず それは”研究”になるものか？ 誰の役に立つ？ 皆が必要性をわかってくれる？ 既存の研究を調べる 誰もまだやっていないから意味がある なぜ重要なのかを知る 研究の流れを掴む どこまでわかっていてどこからわかっていないのか？

卒論の時間は有限 10月 卒論研究室配属 テーマを決めよう 11月 卒論中間発表１回目 12月 卒論中間発表２回目 アブストラクト提出 正月 10月　卒論研究室配属　　　テーマを決めよう 11月 卒論中間発表１回目 12月　卒論中間発表２回目 アブストラクト提出 正月 1月　　卒論中間発表３回目 2月　 卒論発表 3月　　最終提出

関連研究の紹介 離散数学 ゲームツリーサーチ 計算量理論・暗号理論 ゲーム理論 量子計算 有向マトロイド実現可能性判定 ゼロ知識証明 離散数学　 有向マトロイド実現可能性判定 ゲームツリーサーチ 計算量理論・暗号理論　 ゼロ知識証明 ゲーム理論 量子計算 対話証明・隠れ部分群問題・量子ウォーク

今井研 研究紹介 有向マトロイドの実現可能性判定とその応用 中山裕貴 （博士３年） 森山園子 （助手）

有向マトロイド vs. 幾何的表現 ？ ・ 幾何的表現が与えられた場合、対応する有向マトロイドは必ず存在 次元：r , 要素数: n ランク：r , 要素数: n r 個の要素間の 関係の情報のみ保持 例： (r, n) = (3, 6) x y z v1 v2 v3 v4 v5 v6 （符号への抽象化） v1 v2 v3 v4 v5 v6 有向マトロイドの 実現可能性判定問題 ・ 幾何的表現が与えられた場合、対応する有向マトロイドは必ず存在 ・ 有向マトロイドに対応する幾何的表現は必ずしも存在しない ・・・このギャップについて詳しい情報を得たい

有向マトロイドの実現可能性に関する定理 [Richter ‘88, Bokowski and Richter-Gebert ‘90] r = 4, n = 8なる有向マトロイドで、一様なものの総数は 2628個あり、そのうち24個が実現不可能 詳細（用いた手法など）は不明 ・・・ 数を知ったところで応用は難しい [Finschi ’01] による、有向マトロイドの列挙アルゴリズムの提案 ⇒ 有向マトロイドのデータベースが計算機実験に使用可能に 組合せ的対象である有向マトロイドを通し、 代数的性質・幾何的性質の間に新たな結び付けを与える ・ 実現不可能な有向マトロイドの具体的な形が判明 ・ 一様でない有向マトロイドへの拡張が可能に ・ 実現（不）可能性の十分条件となる手法について、 　各手法間の有効性の比較が可能に 代数的手法： BFP [Richter-Gebert ‘92], solvability sequence [Bokowski, Sturmfels ‘86] 幾何的手法： non-Euclidean [Edmonds, Fukuda ‘82], non-HK* [Moriyama, Fukuda, Okamoto ‘04], reducibility [Richter,Sturmfels ‘91]

(r, n) = (4, 8) での実現不可能な 有向マトロイドの個数 一様: χの値が常に 1or -1 #OM(4,8) = 181472 一様なもの 2628 非一様なもの 178844 実現不可能 24 (実現不可能 ??) BFP 24 双二次最終多項式 3944 non-Euclidean 3444 non-Euclidean 18 non-HK* 18 non-HK* 1364 non-Euclidean, non-HK(*): [Fukuda, Moriyama, Okamoto ‘04] BFP: [Nakayama, Moriyama, Fukuda, Okamoto ‘05] さらに、一般の(r, n)についても non-Euclidean ⊆ BFP [Fukuda, Moriyama, Nakayama ‘05]

(r, n) = (4, 8) での実現可能な 有向マトロイドの個数 #OM(4,8) = 181472 一様なもの 2628 非一様なもの 178844 実現可能 2604 (実現可能 ??) reducibility 2593 reducibility ?? solvability sequence 2337 solvability sequence ?? 3 reducibleでなく、solvability sequenceを持つものが３個存在 （r =3の場合は必ず空）

ゲーム、パズル 美添

二人ゲーム、パズルに関連する研究テーマ 探索アルゴリズム パズルの性質の研究 αβ、証明数サーチなどの研究 評価関数の研究(学習など) ソルバーの開発 計算量の研究 組合せゲーム理論など

今井研究室の関連研究 ゲームツリーサーチ パズル/ゲームの計算量の解析 AND/OR木探索アルゴリズムDf-pnの提案とその応用(長井 歩 2002) “Searching for Double Threats in Subproblems of the Game of Go” (美添2005) パズル/ゲームの計算量の解析 “ぷよぷよの全消し判定問題はNP完全” (牟田 2005) “Finding Yozume of Generalized Tsume-Shogi is Exptime-complete” (八登, 瀬田, 伊藤 2005) “Complexity and Completeness of Finding Another Solution and Its Application to Puzzles” (八登, 瀬田 2003)

宣伝 「詰将棋についてはコンピュータが人間を完全に凌駕した」 これは主にDFPN[長井 2002]によるものと言える 長井はIS19期で、今井研のOB 世界最強の詰碁ソルバーもDFPN-(r) [岸本 2005]がベース 岸本もIS19期

研究の背景 : ゲームプレイング プログラム/コンピュータの強さ チェッカー : CHINOOK (Jonathan Schaeffer) 1992, 1994にTinsleyと対戦 オセロ : Logistello (Michael Buro) 1996に世界チャンピオン村上に勝利 チェス : Deep Blue 1997にKasparovに勝利 中国将棋 チェスと将棋の中間の強さらしい 将棋 :激指、 YSS 、IS将棋、Bonanza… アマ五段クラス 角落ちでプロ(勝又五段)に勝利 アマ竜王戦ベスト16 (激指) 囲碁 甘く見て、アマ初段

αβの基本 mini-maxと同じ結果を返すことが保証される αカット、βカットにより探索が省略される 65 35 90 49 62 30 候補手が理想的な順番にソートされていれば、 探索ノード数は元のツリーのノード数のほぼsqrtになる 2倍深く読める [Knuth and Moore 1975] 65 35 90 49 62 30 83 80 Max node Min node

αβの進歩 探索アルゴリズム自体の進歩 PVS, MTD(f), … 評価関数の研究 学習など logistelloなどが有名

対αβ耐性 (こんな言葉はありません、念のため) αβにやられてしまったゲーム チェッカー、オセロ、チェス、中国将棋、・・・ ギリギリ持ちこたえているゲーム 将棋 αβだけではどうにもならないゲーム 囲碁 DFPNなど ???

ゲーム研究の意義 確かに、強くするのが研究目的であるが αβは凄いが、それだけをやっているわけではない それだけじゃつまらない 囲碁は難しいので、囲碁を強くすることができれば、自然と意義のある成果が生まれているはず

囲碁の難しさ 評価関数が存在することがαβの前提 囲碁には適切な評価関数が無い 静的に評価すると不正確 正確に評価するには探索が必要 ここの評価値が知りたい さらなる探索が必要

現在、 僕(美添)が取り組んでいるテーマ 単一の評価関数が作れない場合にどうやって探索を行うか 目指すものは、単純な評価関数の代わりに、いろいろ自動的に探索したり評価したりしてくれる枠組みを作ること 単純な評価関数の組み合わせで評価し、依存関係の解決をする 単純な評価値では無い、確率分布のようなものを元に探索する

副産物 λDFPN Search Algorithm 目標達成までの「手数」を考慮した探索アルゴリズム 証明数を用いた探索アルゴリズムと、threatという考え方を用いたアルゴリズムの融合 囲碁の捕獲探索について、過去のアルゴリズムを凌駕する性能を発揮 論文執筆中・・・締め切りは6月30日

永岡 悟（M1） 高橋 敏明（M1） 上野 賢哉（M2） 計算量理論・暗号理論 永岡　悟（M1） 高橋　敏明（M1） 上野　賢哉（M2）

今井研での最近の研究 暗号理論 ゼロ知識証明 サイドチャネル攻撃 秘密鍵暗号 対話証明系 PCP定理 ストリーム暗号 Unique Game Conjecture ブロック暗号 近似不可能性 一例として 擬似乱数という 観点から概観 量子計算・通信 計算量理論 領域計算量 量子領域計算量 P versus PSPACE L versus P

確率的アルゴリズムの威力 近年のブレークスルー 素数判定問題（２、３、５、７、１１、１３・・・） 無向グラフの連結性判定問題 Solovay & Strassen 1977 Rabin 1980 無向グラフの連結性判定問題 Aleliunas, Karp, Lipton Lovasz & Rackoff 1979 Randomized Polynomial Time Agrawal, Kayal & Saxena 2004 Randomized Logarithm Space t Reingold 2005 s

領域制約アルゴリズムの脱ランダム化 Nisan & Zuckermanの擬似乱数生成器 長さnのシードからnの多項式の長さの乱数列を生成 ランダムに見えてしまう（⇒だませる） シード 乱数列 Randomized Linear Space Logarithm Spaceでも 可能かは未解決 Deterministic Linear Space

擬似乱数 ゼロ知識証明 ストリーム暗号 擬似乱数と暗号の関係 パスワード等の秘密情報を それ自体を相手に渡さずに 保持していることを示す パスポート、 クレジットカード ストリーム暗号 擬似乱数列と平文を １ビットずつXORし暗号化 小規模で高速 携帯電話やBluetooth で採用 単純に作ると 簡単にコピー可能 →擬似乱数を用いて安全に 電子通貨 デジタル署名 電子投票 擬似乱数

３彩色問題を使用したゼロ知識証明の例 1 6 2 3 5 検証者 証明者 4 1.色の対応をランダムに置換 1 5 6 1 3 4 2 6 2 3 5 4 2.色情報を箱に入れ 鍵をかけて送る 3.枝をランダムに１つ選んで送る (1,4) 4.対応する鍵を送る 5.対応する箱を開け異なることを比較

擬似乱数生成とストリーム暗号 ＋ 攻撃 通信 ＋ ＝ ＝ 量子計算・通信との関連 秘密鍵 乱数列 平文 安全性 暗号文 共有 暗号文 秘密鍵 統計的乱数性 非線形性 無相関性 長周期性 線形複雑度 暗号文 共有 攻撃 通信 暗号文 ＋ 秘密鍵 乱数列 ＝ 平文 量子計算・通信との関連 量子暗号を使うと秘密鍵を安全に通信できる （どんなに強力な計算能力をもってしても破れない） 量子計算では、素因数分解などを基礎とした公開鍵暗号系は破られてしまう

ゲーム理論 加藤 公一、牟田 秀俊、西鳥羽 二郎

ゲーム理論とは… 以上の特徴を持つモデルを分析する学問 実用的なおもしろさ 計算量的なおもしろさ 複数の行為主体がいる 各主体が自分の利得が最大となるよう行動する 行動が状況や相手に影響を及ぼす 以上の特徴を持つモデルを分析する学問 実用的なおもしろさ ネットワーク解析 計算量的なおもしろさ Nash均衡点を求める難しさは？

Nash均衡と計算量 3 , 3 10 , 1 1 , 10 8 , 8 とある囚人の話 両方黙秘 片方のみが自白 両方自白 両方とも3年 利得行列(囚人のジレンマ): とある囚人の話 両方黙秘 両方とも3年 片方のみが自白 自白した方1年 黙秘した方10年 両方自白 両方とも8年 B:黙秘 B:自白 A:黙秘 3 , 3 10 , 1 A:自白 1 , 10 8 , 8

Nash均衡と計算量 3 , 3 10 , 1 1 , 10 8 , 8 Bさんが黙秘なら Bさんが自白なら 結局Aさんは自白 Aさんは自白 利得行列(囚人のジレンマ): Bさんが黙秘なら Aさんは自白 Bさんが自白なら 結局Aさんは自白 B:黙秘 B:自白 A:黙秘 3 , 3 10 , 1 A:自白 1 , 10 8 , 8

Nash均衡と計算量 Nash均衡点 3 , 3 10 , 1 1 , 10 8 , 8 同様に考えると Aさんは自白だった Bさんも自白 利得行列(囚人のジレンマ): 同様に考えると Bさんも自白 Aさんは自白だった 結局自白×自白に落ち着く B:黙秘 B:自白 A:黙秘 3 , 3 10 , 1 A:自白 1 , 10 8 , 8 Nash均衡点

OPEN Nash均衡と計算量 Nash均衡点 3 , 3 10 , 1 1 , 10 8 , 8 二行二列は簡単 じゃあ巨大なら？ 利得行列(囚人のジレンマ): 二行二列は簡単 じゃあ巨大なら？ Nash均衡点を求める多項式時間アルゴリズムはあるのか？ OPEN B:黙秘 B:自白 A:黙秘 3 , 3 10 , 1 A:自白 1 , 10 8 , 8 Nash均衡点

研究テーマの例 Nash均衡 他の 均衡点 ネットワーク解析 計算量 ユーザーが利己的な時のスループットの解析 Open Problem: (PとNPの間?) Nash均衡 最適化、凸多面体 他の 均衡点 市場解析等 Nash均衡を求める問題は線形相補性問題で表せる

量子計算・量子情報

背景 量子効果による高速化への限界 量子効果を積極的に利用した計算原理 Shorのアルゴリズム Groverのアルゴリズム 素因数分解 古典の場合と 準指数的なギャップ RSA暗号が破られる　　 Shorのアルゴリズム 素因数分解 Groverのアルゴリズム 非ソートデータの検索

量子暗号 古典暗号だと RSAなど 計算量的安全性 量子計算機を用いて 破られる可能性

量子暗号 量子暗号だと 物理的安全性

隠れ部分群問題 … Shorのアルゴリズムの基本部分は Gが巡回群の隠れ部分群問題 入力：群GとGを定義域とする関数f g1H gkH fにはGの部分群Hに関する制約があり、 fの入力と出力からHを求めたい Shorのアルゴリズムの基本部分は Gが巡回群の隠れ部分群問題 S

量子ウォーク 一言で言えばランダムウォークの量子版 しかしその性能は全く違う ・・・ Glued Tree Start goal ランダムウォークの機能を持ったロボットが左から右に移動するのに・・・ 量子だと 古典だと

対話証明 このような計算モデルで量子の場合の計算能力を見る

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

他の研究機関との関連 今井研 赤門前に オフィスがあるよ ERATO-SORST 量子情報システムアーキテクチャ 企業 他大学 海外