研究
今週いっぱいで四本（うち二本のメインパート執筆）完成させる見込みです．二つも会議の締切がかぶるとかなり辛いですね．
論文書きに熱中していたら査読のことをすっかり忘れていました．自分の詳しいネタについて一本さっくり査読しました．あと2本ほどキューに貯まっています．なぜこうも査読依頼がある時期に集中的に来るのか不思議でなりません．
自分が中心になってやっている研究を一所懸命論文にしています．肝心のネタがまだ進行中という微妙な状況ですが．自分がメインの論文以外に二本ほど書き上げる必要があるので他の論文に関してはひたすら論文読み＆修正です．
Eurocrypt 2009の採録予定論文リストが公開されたようです．
今進めている研究がいい加減煮詰まってきており，最終的に欲しい結果までの証明の道筋が付けれずにいたので，一旦今まで得られた結果プラス新しいオマケの結果をつけた原稿を書き上げて，共著者に送りました．すぐに共著者から返事が来たのですが「オマケの…
今，論文誌へ投稿中の論文が二本あるのですが，半年ほど前に投稿した論文の査読結果が返ってきました．結果として reject されてしまったのですが，内容については評価してくれているので後は査読者の言うように書き方を変更すればOKぽいです．共著者と相談…
採録論文リストが出たようです．気になる論文がちらほらあるので後でざっとまとめようと思います．
PKC 2009 の採録予定論文リストが出たようです．TCC 2009 の論文リストももうすぐ出るはずです．
シンポジウムでの発表がようやく終わりました．少し時間配分を間違えて超過してしまいました．すみません．
明日は某シンポジウムで発表です．Salil Vadhan の論文 "Unified Theory of Pseudorandomness" の解説をする予定です．
少し前ですが，STACS 2009 の採録予定論文が公開されたようです．
STOCの締切が過ぎてしばらく経ちましたが，おそらくSTOCに投稿されたであろう論文がいくつもECCCにアップロードされていました．個人的な興味から特に面白そうなのを挙げておきます． Luca Trevisan, Madhur Tulsiani, Salil Vadhan Regularity, Boosting, a…
量子情報系の会議に招待講演で呼ばれていたので先週末辺りに大阪に行ってきました．最近，量子情報関係の研究をあまりやってなかったので，そっち方面に少し疎くなっていたのですが，良い刺激になりました．
今年の京都賞を受賞された Richard Karp 教授を囲む記念ワークショップが京都であるので，参加のため明日から京都です．
結局，共著者との相談の結果，論文投稿は先送りすることに．残念です．自分のネタは先送りになったのですが，別件で学生さんと共著論文を書くことになりました．
昨日第一稿を書き上げて共著者に送ったところ，スタートとなる仮定が強すぎるので別の簡単な証明があるよ，と指摘されてしまいました．結果の見た目美しさ優先で書いたら失敗．多少泥臭いですがより弱い仮定からスタートしなおした第二稿を書き上げて今しが…
ゴリゴリ書いています．おそらく来月中旬までですが，更新が滞りそうです．招待講演の準備もしなくては．
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…
１０月から新しく助教の方が赴任してきました．専門は微妙に違いますが，計算量理論や暗号理論の似た分野に興味をお持ちらしく，共同研究ができそうです．これからが楽しみです．
ほとんど観光する暇もなく三日ほどで帰国しました．学生さんに発表してもらいましたが，質問責めにあってました．お気の毒．
今日は専攻のM2による中間発表会でした．計算機科学でも実装系などの他分野の研究を聞く機会が普段はないのですが，このような会があると最近の動向を知ることが出来て大変参考になります．さて明後日からアンリ・ポアンカレ研究所で開かれるワークショップ…
Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas Ryan Williams Quantified boolean formula problem （の一般化）がおよそ n log n 時間の非線型下界を持つ，という結果です．QBF問題自体はPSPACEに入ることしか知られていません…
Polynomially secure crypto Michael Backes, Markus Duermuth, and Dominique Unruh CRYPTO 2008 rump session より．要するに逆方向も多項式時間（だけど順方向よりもだいぶ時間がかかる）の一方向関数を仮定無しで構成しましょうというお話のようです（Wo…
暗号系の国際会議へ投稿していた論文が二つほど採録されました．どちらも発表には行けないのですが．また新しい別の計算量理論関係のネタも完成しつつあるので，投稿先を考えないといけません．
計算量理論の基本的事項の復習です．（証明などはたぶん標準的な計算量理論の教科書に載っていると思います．今回は Arora & Barak の新しい教科書の証明方針を参考にしましたが，微妙に細部が異なっているかと思います．間違っていたらご指摘下さい！）長い…
先週まで海外出張していました．来週からは国内出張です．発表準備を急がねば．査読もたまりすぎなので頑張ろう．
今年の第二次査読ブームです．自分がプログラム組織委員を務めている会議の締め切りも終わり，しばらく査読でてんやわんやになりそうです．いつも自分の投稿論文数×３（自分の論文もいつも三人ぐらいの査読者に読んでもらっているので．）の査読を心がけてい…
よくよく考えたら仮定無しで擬似乱数生成器が構成できることに気づきましたが，実は結構単純であんまり面白いとは言えない結果になってしまいました．共同研究者がまた別の面白い方針を教えてくれたので，そちらを取り組むことに．
