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

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

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

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

最近，ある意味 extreme な科学系ニュースがいくつか飛び交っていますね． Gizmode： ついに常温核融合を成功させた科学者は日本人 北海道新聞： 簡易炉で「常温核融合」か 北大院・水野氏が確認 国際学会で発表へ Gigazine： 水から電流を取り出すことを可…

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

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

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