平均計算量理論の研究を現在進行形でやってるわけですが，基本的な知識に抜けが多すぎるので，このサーベイ論文で勉強しなおすことにしました． A. Bogdanov and L. Trevisan, "Average-Case Complexity" 平均計算量の基本的な概念や重要な結果が分かり易く…

今年のTuring賞受賞者が決まったみたいですね． Frances E. Allen For pioneering contributions to the theory and practice of optimizing compiler techniques that laid the foundation for modern optimizing compilers and automatic parallel executi…

最近 accepted paper list ばっかり載せていますが，今回はSTOC 2007です．量子計算関係（だと思われるもの）は以下の４本でした． F. Magniez, A. Nayak, J. Roland and M. Santha, "Search via Quantum Walk." D. Gavinsky, J. Kempe, I. Kerenidis, R. Ra…

採録論文リストが出たようです． 個人的には Secure Computation from Random Error Correcting Codes H. Chen, R. Cramer and S. Goldwasser, R. de Haan and V. Vaikuntanathan が気になります．最近はボスとの共同研究で平均計算量絡みの研究で忙しいです…

次回の Computational Complexity Conference の採録論文リストが公開されたみたいです．