今，論文誌へ投稿中の論文が二本あるのですが，半年ほど前に投稿した論文の査読結果が返ってきました．結果として 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 の新しい教科書の証明方針を参考にしましたが，微妙に細部が異なっているかと思います．間違っていたらご指摘下さい！）長い…

先週まで海外出張していました．来週からは国内出張です．発表準備を急がねば．査読もたまりすぎなので頑張ろう．

今年の第二次査読ブームです．自分がプログラム組織委員を務めている会議の締め切りも終わり，しばらく査読でてんやわんやになりそうです．いつも自分の投稿論文数×３（自分の論文もいつも三人ぐらいの査読者に読んでもらっているので．）の査読を心がけてい…

よくよく考えたら仮定無しで擬似乱数生成器が構成できることに気づきましたが，実は結構単純であんまり面白いとは言えない結果になってしまいました．共同研究者がまた別の面白い方針を教えてくれたので，そちらを取り組むことに．

すごく強力な擬似乱数生成器を構成したのですが，仮定がエグすぎ（おそらく成立しない）なので，どうしたものか暫く悩んでます．共同研究者に知恵を借りよう．

気がついたら既に今年のゲーデル賞受賞者が Shanghua Teng と Daniel Spielman の二人に決まったようです．線型計画法における計算量の均し解析が評価されたようです． ACM-SIGACTの公式ページにはまだ載ってないのですが，Wikipediaには既に載っていたりし…

FOCS 2008 の採録予定論文が出た模様です． Timothy Chow Almost-natural proofs が気になって探してみたところ本人のページにおいてありました．７ページの短い論文でRazborov-Rudichの結果を拡張しているっぽいです．NIIの小林さんと松本さんの論文も通っ…