特に問題なくたどりつきましたのでご心配なく．Ｏ本さんからのお土産のカイコを食べ過ぎて何となく虫臭いです．

さて前回のエントリーの続きです．EXP=NEXPだった場合にはNEXP探索問題は指数時間で解けそうもない，ということでした．NP=Pの場合には降下型自己帰着によりNP探索問題はNP=Pの場合には多項式時間で解けるのですが，なぜ同じアプローチは通じないのでしょう…

妻が赤ちゃんにかかりきりなので，私がよく夕食を作ったりしているのですが，これを期にいろいろな料理に挑戦しています．今日はネタフルのこの記事に触発されて揚げ鶏の葱ソースかけを作ってみました．揚げ物って初めてやってみたのですが油の温度調整とか…

NP問題は良く知られているように降下型自己帰着(downward self-reduction)を持ちます．つまり，長さ以下のインスタンスの判定を行うオラクルがあれば，多項式時間で長さのインスタンスの判定を行うことが可能，ということです．分かり易い例でいうと充足可能…

結局残り一割のところにミスが見つかり，まわりまわって結局正しくなりそうなので，さらに証明をつめていく作業に入っています．日中は家事と我が子の世話をしつつ，彼が寝ている隙に研究を進める毎日です．

育児の合間に新しいネタを仕上げつつあります．（他にも科研費の報告書書きやらジャーナル投稿論文の修正作業やらあるのを尻目にですが・・・）九割方証明を終えてはいるのですが，いつも残り一割に落とし穴があるのです．慎重に詰めていかねば．しかしFOCS…

Trevisan のとこの博士課程学生の James Cook がかの Stephen Cook*1 の息子だったとは．知らんかった． *1:Cook-Levin Theorem の Cook です．

やはりあと一歩のところでダメでした．でもアプローチとしては悪くなさそうなので，もう少し頑張ってみようと思います．

四半世紀ぐらい未解決の結構有名な予想が解決できた気がします．二日ほどしか考えていないのですが，本当に解決できたのか自分でも半信半疑なので慎重に証明を進めてみようと思います．

子どもをあやしながらSkypeで学生の論文執筆指導．便利な世の中になったものです．

今年はライダーマンだったようです．なんとYahoo!のトップ絵になってますね．でも今の受験生世代ってライダーマンとか知っているのでしょうか．仮面ライダーSPIRITSに出てきているようですが（未読）なおこの漫画でもライダーマンの活躍が読めます．早く続き…

今更ですが，STOC 2009 の採録予定論文リストが公開されているようです．今回はアブストラクト付きです．

先週の金曜日に論文締切だったわけですが，実はその当日に長男が誕生しました．前日朝から妻の陣痛が始まり，それからおよそ1日半ほどの長い時間が出産にかかりました．その間ずっとそばで付き添っていたのですが，そんな長く辛い出産でも妻が頑張ってくれた…

と論文執筆にかまけていたら査読の催促が．すみません，ちょっと待って下さい．来週の頭までには・・・

今週いっぱいで四本（うち二本のメインパート執筆）完成させる見込みです．二つも会議の締切がかぶるとかなり辛いですね．

論文書きに熱中していたら査読のことをすっかり忘れていました．自分の詳しいネタについて一本さっくり査読しました．あと2本ほどキューに貯まっています．なぜこうも査読依頼がある時期に集中的に来るのか不思議でなりません．

自分が中心になってやっている研究を一所懸命論文にしています．肝心のネタがまだ進行中という微妙な状況ですが．自分がメインの論文以外に二本ほど書き上げる必要があるので他の論文に関してはひたすら論文読み＆修正です．

Eurocrypt 2009の採録予定論文リストが公開されたようです．

今進めている研究がいい加減煮詰まってきており，最終的に欲しい結果までの証明の道筋が付けれずにいたので，一旦今まで得られた結果プラス新しいオマケの結果をつけた原稿を書き上げて，共著者に送りました．すぐに共著者から返事が来たのですが「オマケの…

明けましておめでとうございます．新年早々風邪を引いてこじらせてしまいました．一週間ほどダウンです．