16時30分～17時30分
講 演 者：川原　純（奈良先端科学技術大学院大学　情報科学研究科　助教）
講演題目：「大規模データ処理のための離散構造処理系」
講演概要：本講演では，大規模データ処理のための離散構造処理系，特に，集合族をコンパクトに効率良く表現するためのデータ構造であるゼロサプレス型二分決定グラフ (ZDD) について解説を行う．ZDDを用いると，与えられたグラフの様々な種類の部分グラフを効率良く列挙し，索引化することが可能となる．例えば，15 × 15 グリッドグラフ上の左上隅から右下隅に至るパス227449714676812739631826459327989863387613323440（= 2.27 × 1047）本を数分で列挙，保存し，それらの中から指定した条件を満たすパスを高速に検索することができる．他にも，全域木やマッチング等に対しても本手法が適用できる．通信ネットワークの信頼性評価や，配電網の構成法等への応用事例も紹介する．

17時30分～18時30分
講 演 者：河内 亮周（東京工業大学　大学院情報理工学研究科　助教）
講演題目：「回路計算量の不思議」
講演概要：計算機で扱う問題の計算の複雑さを議論するとき，計算量理論は計算機の理論モデルとしてTuring機械をよく扱うが，その他のモデルとして論理回路もしばしば議論の俎上に載せる．論理回路は定義が単純で扱い易く，実際にNP対P予想解決への正攻法の一つが回路計算量（問題を解くのに必要十分な回路サイズ＝素子数）の解析である．その一方で論理回路にはTuring機械にはない謎の計算能力が備わっている．例えば指数サイズ回路は任意の関数（Turing機械が計算不能な関数ですら！）計算でき，また現状では指数時間Turing機械を多項式サイズ回路で模倣できてしまう可能性すら排除できていない．このような謎の能力がどこから来るかを説明し，それをどのように解析していくのか，NP対P予想への最新アプローチの話も織り交ぜながら解説を行いたい．