タイトル: ACC^0回路のNEXPでの超多項式下界の解説
講師: 河内 亮周 (東工大)
場所: 計算限界研究センターセミナー室
http://www.al.ics.saitama-u.ac.jp/elc/?celc
関連論文:
[Wil13] Ryan Williams: Natural Proofs versus Derandomization, manuscript (available at R. Williams' website).
[Wil11] Ryan Williams: Non-uniform ACC Circuit Lower Bounds. IEEE Conference on Computational Complexity 2011: 115-125
[Wil10] Ryan Williams: Improving exhaustive search implies superpolynomial lower bounds. STOC 2010.
[IKW02] Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: In search of an easy witness: exponential time vs. probabilistic polynomial time. J. Comput. Syst. Sci. 65(4): 672-694 (2002)