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

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

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

どうやら alternation を randomenss に変換するのは結構大変なようです．目だった結果としては Sipser の ぐらいみたいですね．こう見ると randomness というのはかなり特殊な計算資源なんだなー．

まだ交代性Turing機械になりきれていないようです．量子計算機になりきれていなかった時代を思い出しました．日々精進です．

ここ一週間で二本ほど論文執筆＆投稿してました（どちらも主著者ではありませんが）．最近連敗気味なので好転すると良いのですが．

前回のエントリの続きです．さて Gowers norm というものが計算量理論でいろいろ応用できることを簡単に触れました．その Gowers norm の顕著な特徴として，高次の Gowers norm では低次多項式の影響が失われる，というものがあります．より具体的には，任意…

前回のエントリの肝心の中身について書こうと思います．そもそも Gowers uniformity norm というのは Gowers が Erdos-Turan conjecture の(Szemerediの定理として知られている)ある特殊ケースの別証明のために導入した概念です．一般的には以下のように定義…

Shachar Lovett, Roy Meshulam, Alex Samorodnitsky Inverse Conjecture for the Gowers norm is false 解説を少し書こうと思いましたが，書類書きで疲れているので明日中身を書きます．（これだけでも書いておくと自分へのプレッシャーにはなりそうです．）

Internet WATCH の記事，産総研とヤフー、フィッシング防止技術の評価用ソフトウェアを公開，より 産業技術総合研究所（産総研）とヤフーは22日、フィッシング詐欺の防止技術「HTTP Mutualアクセス認証」を組み込んだWebブラウザ「MutualTestFox」と、Webサ…

しばらく香港にいます．

Terence Tao and Van Vu, "On random matrices: Singularity and Determinant" Terence Tao and Van Vu, "On the singularity probability of random Bernoulli matrices" 最近，（あまり進んではいないのですが）ランダム行列の解析に興味を持っていまして…

なんかバンバン来てます．これはまずいです．査読のペースを上げなければキュー長が発散してしまいそうです．

IWSEC 2008 の開催地が香川と聞き，これは讃岐うどんをしこたま食べられるチャンスだと随分前から考えていたのですが，投稿締め切りが次の金曜日と迫っているのにも関わらず良いネタが手元にありません．これは残念．

accepted paper list がトラックA,B,Cともに揃ったようです．

一件終わらせたらまた一件依頼が来ました．FIFOで頑張ります．

今年も査読の季節がやって参りました．まだ今のところ２件だけですが．

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 の結果が改良できたと思うのですが，まだ詳細を詰めることができていません．早めに証明を完成させねば．

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

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

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

少し前に国際会議で発表した論文の論文誌版を今編集しているところなのですが，毎回どこに投稿するか悩みます．論文誌の評価などを調べているうちに良いサイトがあったことを思い出しました． CiteSeer Statics Estimated impact of publication venues in C…

Computational Complexity Weblog の2/14の記事を発端に 186::Diary や 偽らざるもの でも話題になっていますが，worst/average-case connection を持つ問題を暗号のベースとすることについての是非について私見を少し述べたいと思います．186::Diary でコメ…

一年前から温めていたネタをとうとう投稿しました．といっても実は半年前から全然進展していなかったのですが．いつまでも未解決問題を抱えっぱなしというわけにもいかないので一旦とりまとめたといったところです．また来週に一本投稿しなければ．

Papers accepted to STOC 2008 偽らざるもの：STOC 2008 accepted papers 186::ダイアリー：STOC 2008のリスト 京大の玉木さんから Anup Rao が Raz の parallel repetition theorem を（去年 Holenstein が簡単化したのを）さらに簡単化した，という話を聞…

ドイツのLuebeck大学から Maciej Liskiewicz 先生をお迎えする機会がありまして，セミナーで最近の研究のお話をして頂きました．内容は cheat sensitivity という安全性概念を考えて，その安全性を満たすような oblivious transfer や bit commitment protoc…