>>> Complexity Seminar のお知らせ <<< （またまた急で申し訳ありません）

現在，客員研究員として本専攻にいらしている Koebler 先生が，以下の
講演をして下さることになりました．是非，ご参加下さい．

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

題目: On the Average-Case Complexity of NP and Other Problems
講演者: Johannes Koebler (Humbolt Univ. at Berlin)

We show that not all sets in NP (or other levels of the
polynomial-time hierarchy) have efficient average-case algorithms
unless the Arthur-Merlin classes MA and AM can be derandomized to
NP and various subclasses of P/poly collapse to P.  Furthermore,
other complexity classes like P(PP) and PSPACE are shown to be
hard on average unless they are easy in the worst case.

以上