戸田の定理の簡潔な証明

研究

Lance Fortnow の論文リストを見ていたらこんな論文が．

  • Lance Fortnow
    • "A simple proof of Toda's theorem," Theory of Computing, 5(7):135-140, 2009.

所謂 "Toda's Theorem" というのは " PH \subseteq P^{\sharp P}" という結果ですが，この論文ではその前半部分である " PH \subseteq BPP^{\oplus P}" を半ページ（但し既存の結果を引用した上でですが）で済ませています．ちなみに後半部分についても解説が書かれているので興味がある方は是非読まれることをお勧めします．

stacs.cls

研究

かの著名な国際会議STACSは数年前からLNCSを離れて自前で会議録を出版していることは皆さんご存知かと思います．今回初めてSTACSフォーマットで投稿することを考えているのですが，幾分慣れていないので，自分用の防備録としてでもTipsを残しておこうと思います．

  • \cal は未定義なのでプリアンブルに \newcommand{\cal}{\mathcal} を追加しておけばOK
  • 自然数の集合 \nat (\mathbb{N})や整数の集合 \integer (\mathbb{Z}) が未定義なので \newcommand{\nat}{\mathbb{N}} 等，プリアンブルに追加しておけばOK
  • ACM classification code はココを参照

ちなみにサンプルファイルの Abstract で引用されている (Emerson, Lake, and Palmer, 1973) はコレです．

ISAAC 2009 Accepted Paper List

研究

12月開催予定のISAAC 2009の採録予定論文リストが出たようです．参加する予定はないのですが，ハワイであるみたいですね．楽しそうです．招待講演に Ronald Graham の名前がありますねー．どういう講演だったか参加した人にあとで教えてもらおうと思います．

さて採録予定論文の中で個人的に

  • George Karakostas, General pseudo-random generators from weaker models of computation

が気になったので調べてみたところ，単調回路を騙すための擬似乱数生成器の構成方法について書かれている様子でした．同じように明示的に指数的回路計算量が証明できている定数段回路に対する脱乱化の結果は結構たくさんあるのですが，単調回路についてはあまり知られていないのではないでしょうか．この研究方針は結構狙い目かもしれません．

講演依頼

研究

10月初旬に大阪で計算量理論の入門について専門外の方々に講演することになりました．情報オリンピックの合宿でやった話をアレンジしようと思っています．以前のは高校生向けだったので，少し専門性の高い話題も入れようと思います．