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

   日時  ：３月２８日（金）１６：００〜
   場所  ：東京工業大学 南３号館 ２階 電気情報系会議室
   連絡先：03-5734-2688
           計算工学専攻 渡辺 治（南３号館 ９階 ９１８号室）

   Title: AN ALGEBRAIC POINT OF VIEW ON CIRCUIT COMPLEXITY
   By: Denis Therien (McGill Univ.)

   Abstract:
   Consider circuits and expressions whose gates carry out
   multiplication in some algebraic structure.  Given a circuit
   (or an expression) and truth values for the inputs,
   determining the truth value of the output is called the
   CIRCUIT VALUE (or EXPRESSION EVALUATION) problem.
   These questions are deeply related to the complexity classes
   P and NC^1.

   In this talk, we will review what is known when the underlying
   algebra is associative, including the famous theorem of
   Barrington relating NC^1 and bounded width branching programs.
   We will also present new results discussing the non-associative
   case.