>>> Complexity Seminar のお知らせ <<<

先日，ご案内したセミナーの内容をお送りします．是非，ご参加下さい．

   日時：１２月１２日（金），午後４時３０分より１時間ほど
   場所：西８号館 (W) 10 F コラボレーション・ルーム

   題目：Graph Isomorphism is in SPP
   講演者： Piyush Kurur (Tata Inst. of Tech.)

Given two graphs the problem of testing whether they are isomorphic
has attracted lots of research. Even though no polynomial time
algorithm is know for this problem there are evidences that suggest
that graph isomorphism cannot be hard for NP. For instance GI is in
$\textrm{AM} \cap \textrm{co-AM}$.

In this talk we show that graph isomorphism problem is in the
complexity class SPP. As a result GI is in and low for complexity
classes like $\oplus\textrm{P}$, $\textrm{Mod}_k\textrm{P}$ etc. We
also show that the hidden subgroup problem (of interest in quantum
computing) over permutation groups has an $\textrm{FP}^\textrm{SPP}$
algorithm.

This is joint work with V. Arvind.

Keywords: Graph isomorphism, permutation groups, hidden subgroup
          problem.

以上