2013年度第1回 ELC領域会議
日時：6月13日9:00～6月14日11:20
場所 : 京都大学本部キャンパス
6月13日午前: 総合研究4号館 1階 共通2
6月13日午後: 総合研究8号館 3階 Sホール
6月14日: 総合研究7号館 1階 情報2講義室
プログラム
６月１３日 午前 (場所：総合研究4号館 1階 共通2)
９：００～９：３０ 領域の方向性：渡辺領域代表、事務局連絡
９：３０～９：４５ A01班
９：４５～１０：００ A02班
１０：００～１０：１５ A03班
１０：１５～１０：３０ 休憩
１０：３０～１０：４５ B01班
１０：４５～１１：００ B02班
１１：００～１１：１５ B03班
１１：１５～１１：３０ C01班
１１：３０～１１：４５ C02班
１１：４５～１２：００ C03班
昼休み
６月１３日 午後 (場所：総合研究8号館 3階 Sホール)
１３：００～１３：１５ 公募研究班 Skip Jordan (北海道大学)
１３：１５～１３：３０ 公募研究班 宇野 裕之 (大阪府立大学)
１３：３０～１３：４５ 公募研究班 安永 憲司 (金沢大学)
１３：４５～１４：００ 公募研究班 泉 泰介 (名古屋工業大学)
１４：００～１４：１５ 公募研究班 塩浦 昭義 (東北大学)
１４：１５～１４：３０ 休憩
１４：３０～１４：４５ 公募研究班 森山 園子 (東北大学)
１４：４５～１５：００ 公募研究班 山中 克久 (岩手大学)
１５：００～１５：１５ 公募研究班 伊藤 健洋 (東北大学)
１５：１５～１５：３０ 公募研究班 永田 賢二 (東京大学)
１５：３０～１６：００ 休憩＆ポスターセッションの準備
１６：００～１８：００ ポスターセッション
（注：１７：００より総合研究8号館 3階 Nホールにて総括班会議を開催）
懇親会
時間 １９：００～
場所: 百万遍 しゃらく
http://r.gnavi.co.jp/k614100/map/
６月1４日（場所：総合研究7号館 1階 情報2講義室）
９：００～ ９：４０ 講演： 脊戸 和寿 (電気通信大学)
９：４０～ ９：５０ 休憩
９：５０～１０：３０ 講演： 上野 賢哉 (京都大学)
１０：３０～１０：４０ 休憩
１０：４０～１１：２０ 講演： 内澤 啓(山形大学)
脊戸 和寿 (電気通信大学)
タイトル： Circuit Satisfiability
アブストラクト： Circuit Satisfiability (CktSAT)とは与えられた論理
回路の出力が1になる入力割当が存在するかどうかを判定する問題である．これは
有名なNP完全問題の1つであり，入力変数の多項式時間では解けそうにない．
それどころか，一般の多項式サイズの回路が与えられるとその充足可能性判定には，
2^n時間必要であると思われている．2010年，Ryan WilliamsはCktSATが2^n
よりも超多項式的に高速にとけるなら，NEXPが多項式サイズの回路をもたないことを
示した．(NEXP not in P/poly) さらに，ある特定の回路クラスCに制限した
CktSAT (C-SAT)が同じように高速にとけるなら，NEXPが多項式サイズのクラスCの
回路をもたないことも示している．(NEXP not in C) これ以降，CktSATに対する
研究は加速し，様々なC-SATに対するアルゴリズムが開発された．現時点でCktSATの
アルゴリズムの開発によって計算量クラスの分離に成功したのは，Ryan Williamsの
NEXP not in ACC0のみであるが，多くのC-SATの結果に付随して，Average
Case HardnessやCorrelation Boundが示されている．これは一種の計算限界を
示すものである．本発表では，一連のCktSATの結果を紹介し，今後の展開について述べる．
上野 賢哉 (京都大学)
タイトル： 非平衡な再帰関数の計算限界
アブストラクト：再帰的に定義された論理関数に対して，論理式サイズ下界を証明する
方法として量子敵対者法を説明し，再帰が非平衡な場合への適用を考えるとともに，
下界証明に対する一般的な証明限界について議論する.
内澤 啓 (山形大学)
タイトル： 論理回路の出力パターン数とその応用
アブストラクト：論理回路とは，AND素子やOR素子などの論理素子を基本素子とする
組合せ回路である．入力が与えられた時に論理回路が行う計算は，回路を構成する
各素子の出力値の組合せ，即ち，出力パターンとして表現できる．ここで，ある回路に
現れる出力パターンの種類の総数を，その回路の出力パターン数と呼ぶ．本講演で
は，この回路の出力パターン数を解析することによって得られる論理回路の下界や，
その他の応用について述べる．
|