Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas Ryan Williams Quantified boolean formula problem （の一般化）がおよそ n log n 時間の非線型下界を持つ，という結果です．QBF問題自体はPSPACEに入ることしか知られていません…

Polynomially secure crypto Michael Backes, Markus Duermuth, and Dominique Unruh CRYPTO 2008 rump session より．要するに逆方向も多項式時間（だけど順方向よりもだいぶ時間がかかる）の一方向関数を仮定無しで構成しましょうというお話のようです（Wo…

今朝，布団の中で不意に天下一品のスープの味を思い出したので，近所の支店に食べに行きました．学生の頃，京都に住んでいたので天下一品にはちょくちょく通っていたのですが，就職してからはほとんど食べていませんでした．それにも関わらず，明確に味を思…

暗号系の国際会議へ投稿していた論文が二つほど採録されました．どちらも発表には行けないのですが．また新しい別の計算量理論関係のネタも完成しつつあるので，投稿先を考えないといけません．

計算量理論の基本的事項の復習です．（証明などはたぶん標準的な計算量理論の教科書に載っていると思います．今回は Arora & Barak の新しい教科書の証明方針を参考にしましたが，微妙に細部が異なっているかと思います．間違っていたらご指摘下さい！）長い…