Information-Theoretic Conditions for Two-Party Secure Function Evaluation Claude Crépeau, George Savvides, Christian Schaffner, Jürg Wullschleger EUROCRYPT 2006 の論文です．これまで提案されてきたいくつかの情報理論的安全性に関する二者間の安…

明日は量子計算絡みのワークショップで発表です．久しぶりに量子関係の話をすることに．ちょっと不安です．

スラッシュドットジャパン 40年近く答えの出なかった数学の難問が解かれる 昨日の記事ですが，Road Coloring Problem (Road Coloring 予想) と呼ばれるグラフ理論の定理が証明された事の紹介があったようです．グラフ理論については不勉強なもので今までこの…

最近忘却通信がらみの研究をやっているのですが，奥の深さに感心しています．安全性の定義だけでもかなりの紆余曲折があったみたいですね．

BPP の derandomization に関する Impagliazzo-Wigderson の結果が改良できたと思うのですが，まだ詳細を詰めることができていません．早めに証明を完成させねば．

明日の中高生向けの講義の準備が一応完了しました．三時間分新たに書き下ろしたので結構大変でした．NP vs. P 予想，ゼロ知識証明，PCPの話を紹介する予定です．帰着の概念の説明に良い具体例が見つかっておらずちょっとモヤモヤですが．

理由あって最近ギターを久しぶりに練習してます．暫く弾いてないと駄目ですねー．

三月中旬に量子計算関係のワークショップで発表しなくてはいけないことを思い出しました．最近学生さんと一緒にやっていることを話そうと思いますが，結果が間に合うかどうか．

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

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