第五回計算量理論若手の会ワークショッププログラム

場所:九州大学西新プラザ小会議室
日程:2012年9月17日〜18日


9月17日 10:00-18:00
発表者:河内 亮周(東工大)
タイトル:NEXP⊂P/polyならばNEXP=MAおよびその応用としてのACC0の超多項式サイズ下界
概要:2011年Ryan Williamsによって長年未解決であった明示的な関数に対するACC0の 超多項式サイズ下界が与えられた衝撃も記憶に新しいが[Wil11],この結果が大きく依存しているのが Impagliazzo, Kabanets, and Wigdersonによる"NEXP⊂P/polyならばNEXP=MA"を示した論文[IKW02] で導入された技法である.本発表では,学部レベルの計算量理論の知識のみを前提に, [IKW02]で導入された技法,そしてそれを応用して[Wil11]の結果を理解することを目指す.



9月18日 10:00-15:00
発表者:玉置 卓(京都大)
タイトル:相対化不可能な証明手法
概要:本発表では相対化不可能な手法を使って証明された"EXP⊂P/polyならばEXP=MA"[BFL91]を解説し, その理解を目指す.(実質的には"MIP=NEXP"の証明を紹介する.)またその背景を [AW09],[AIV],[For94]の結果を要約して解説を行いたい.

参加者の皆様へ
河内の講演については予め以下の原稿を持参されることをお勧めします.

玉置さんの講演については参考文献[AIV,AW09,BFL91,For94]を持ってきてもよいしなくても大丈夫とのことです.(文責:河内)