計算量理論の研究をやっているのにも関わらず，多項式階層について今までほとんど手を付けていなかったことに後悔しています．これは奥深いですね．多項式階層どころかクラスcoNPを考える機会すらあまりなく，研究に直観が追いつかない状況です．良い機会な…

今，Emanuele Viola の論文(Computational Complexity, 2004)を読んでいるのですが，その中に Trevisan の有名な結果*1，擬似乱数生成器(pseudorandom generator: PRG)から乱数抽出器(extractor)を構成できることの証明の解説が載っていました．案外単純だっ…

今年の折田先生像はてんどんまんだった模様です． GIGAZINE 京都大学入試シーズンの風物詩・折田先生像、今年は「てんどんまん」 京大もオフィシャルにこんなページを出しています．さすが京大ですね・・・

高校生相手に三時間ほど計算量理論の入門編を講義することになりました．NP vs. P 予想の話でもしようかなと思います．

少し前に国際会議で発表した論文の論文誌版を今編集しているところなのですが，毎回どこに投稿するか悩みます．論文誌の評価などを調べているうちに良いサイトがあったことを思い出しました． CiteSeer Statics Estimated impact of publication venues in C…

Computational Complexity Weblog の2/14の記事を発端に 186::Diary や 偽らざるもの でも話題になっていますが，worst/average-case connection を持つ問題を暗号のベースとすることについての是非について私見を少し述べたいと思います．186::Diary でコメ…

一年前から温めていたネタをとうとう投稿しました．といっても実は半年前から全然進展していなかったのですが．いつまでも未解決問題を抱えっぱなしというわけにもいかないので一旦とりまとめたといったところです．また来週に一本投稿しなければ．

Papers accepted to STOC 2008 偽らざるもの：STOC 2008 accepted papers 186::ダイアリー：STOC 2008のリスト 京大の玉木さんから Anup Rao が Raz の parallel repetition theorem を（去年 Holenstein が簡単化したのを）さらに簡単化した，という話を聞…

ドイツのLuebeck大学から Maciej Liskiewicz 先生をお迎えする機会がありまして，セミナーで最近の研究のお話をして頂きました．内容は cheat sensitivity という安全性概念を考えて，その安全性を満たすような oblivious transfer や bit commitment protoc…

SCIS 2008の公式ページをチェックしたら論文賞の情報が出ていました．知り合いが二人ほど受賞しているようです．（お二人とも優秀な博士課程の学生さんです．）米山さん，草川さん，受賞おめでとうございます．

旧年中は本当にたくさんの方々にお世話になりました．今年も引き続きよろしくお願い致します．早速近所の目黒不動尊に初詣に行ってきましたが，すごい人出でした．日本人って結構信心深いのかも知れませんね．