以前ちょっと小耳には挟んでいたのですが，NP≠Pの証明へのアプローチの難しさを示す結果が最近（といってもすでに二ヶ月ぐらい前ですが）AaronsonとWigdersonによって示されたようです．まだ論文自体は公表されていませんが，Aaronsonのブログのこの記事から…

同じ研究分野の某研究者のウェブページにて私が現在投稿中の論文とモロ被りのタイトルの論文がPKC 2008 に採録されているのを発見してしまいました．（ちなみに採録予定論文はまだオフィシャルサイトでは公開されていないようです．）まだ論文自体はどこにも…

ジョジョの奇妙な百人一首微妙に欲しいです．

最近Gowers uniformity normを使ってとある計算複雑さの評価を試みていたのですが，そんな高級な道具を使わなくとも昔から良く知られているフーリエ解析的手法で非常にあっさりと評価できてしまうことに気がついてしまいました．あまりにも捻りがなくてその…

TCC 2008 の採録予定論文一覧が出たようです．日本からはNIIの小林さんの量子ゼロ知識証明の論文が採録されてますね．おめでとうございます．

Terence Tao が今年の FOCS で行ったチュートリアル講演の内容のドラフトをたまたま見つけました． Terence Tao, "Structure and randomness in combinatorics" アップロードされたのは今年の夏のようです．内容としては関数のもつ構造と擬似乱数性の関係を …