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

 　日時：１１月２１日（木），３時半〜６時頃
 　場所：東京工業大学 南３号館 電気情報系会議室

 　題目：近似法の可能性（と限界）

   発表： Kazuyuki Amano (Tohoku Univ.)

　 概要：

     1985 年に Razborov がクリーク関数を計算する単調論理回路のサイ
     ズに対する超多項式下界（後に，Alonらによって指数関数下界へと
     改良された）を証明した際に用いられた手法は，後に近似法と呼ば
     れ，その後も単調論理回路のサイズの下界に関する幾つかの結果を
     示す際に用いられてきました．本講演では，まず，この近似法につ
     いて解説し，この手法に関する最近の結果などについて概説します．
     次に，最近我々（天野と丸岡）が発表したクリーク関数に対する指
     数関数下界を与える，近似法を用いた新たな証明について解説しま
     す．また，近似法で否定ゲートを含む回路を取り扱おうという試み
     についても紹介する予定です．