ゴリゴリ書いています．おそらく来月中旬までですが，更新が滞りそうです．招待講演の準備もしなくては．

SODA 2009のプログラムが公開されたようです．B. Chazelle の "Natural Algorithms" という論文タイトルがキャッチーですね．中身が気になったのですが，ウェブ上では見つかりませんでした．

前回のエントリの続きです．言語に対してそのYESインスタンスを入力として与えられたときに，そのに対する証明集合[tex: R_x = \{ w\in\{0,1\}^m: \in B_L \}] （はの多項式，はについて与えられたインスタンスと証明の二項関係）から一様ランダムに取ってく…

M. Bellare, O. Goldreich and E. Petrank Uniform Generation of NP-Witnesses Using An NP-Oracle で任意のNP問題の証明を一様ランダムにサンプリングしようという結果です．Jerrum, Valiant, Vazirani の結果でも同様のことができますが，その結果ではNP…

１０月から新しく助教の方が赴任してきました．専門は微妙に違いますが，計算量理論や暗号理論の似た分野に興味をお持ちらしく，共同研究ができそうです．これからが楽しみです．

二年生のプログラミング演習は昨年度まで半分担当してもらっていた先輩助教の方が栄転されたこともあり，一人で担当することに．今年は準備が大変そうです．三年生の演習はマルコフ連鎖モンテカルロ法の勉強をしてもらおうと思います．

ほとんど観光する暇もなく三日ほどで帰国しました．学生さんに発表してもらいましたが，質問責めにあってました．お気の毒．