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

場所:山形県米沢市旅館春木屋会議室
日程:2013年9月11日〜13日


9月11日

13:30-15:30 玉置 卓(京都大) Parallel Repetition of Two Prover One Round Games
16:00-18:00 未解決問題セッション


9月12日

10:00-12:00 河内 亮周(東工大) Proving Circuit Lower Bounds in High Uniform Classes
12:00-13:30 昼休み
13:30-14:30 長尾 篤樹(京都大) Read Once Branching Programs for Tree Evaluation Problems
15:00-16:00 森 立平(東工大) Introduction to Channel Polarization
16:30-17:30 安永 憲司(金沢大) Error correction in computationally bounded channels


9月13日

10:00-12:00 内沢 啓(山形大) Energy Complexity of Threshold Circuits



チュートリアル


9月11日
発表者:玉置 卓(京都大)
タイトル:Parallel Repetition of Two Prover One Round Games
概要:P と NP が異なるという仮定の下で、Max 3SAT, Max Clique, Set Cover など様々な問題の最適な近似不可能性が知られている。 そのような近似不可能性の結果は Two Prover One Round Games と呼ばれる組合せ最適化問題の近似不可能性に帰着することで示される。 本発表では Two Prover One Round Games の近似不可能性証明の重要な構成要素である Parallel Repetition Theorem の紹介を行う。


9月12日
発表者:河内 亮周(東工大)
タイトル:Proving Circuit Complexity in High Uniform Classes
概要:NP vs. P 問題を解決するための王道はNPに属する問題の 回路計算量の超多項式下界を証明することであるが,これは非常に困難である. その目標の緩和の一つとして回路計算量下界の研究ではNPより高いクラスで 下界を証明することが活発に行われている.この講演ではその主だった手法を 解説したい.


9月13日
発表者:内沢 啓(山形大)
タイトル:Energy Complexity of Threshold Circuits
概要:しきい値回路とは神経回路網の理論モデルの一つであり, エネルギー複雑度とは神経回路網の消費エネルギーの仕組みに基づいて 提案された,しきい値回路の新しいパラメータである. この講演では,しきい値回路のエネルギー複雑度に係る主要な結果を紹介するとともに, 結果の導出手法について概説する.