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

  日時： 11 月 9 日（木），午後 3:30 - 6:30
  場所： 東京工業大学 本館 H136 講義室
        （本館３Ｆ正面に対して一番左の廊下の最も奥）

  題名： On Shifting Networks over Parity Gates 

  発表者： Tatsuie Tsukiji（東工大）

  内容：

   We show nonlinear lower bounds on Boolean circuits of depth O(log n)
   using only parity gates, which compute shifts of n inputs.

   The combinatorial achievement of the paper is as follows.  Let M be a
   n by n regular Boolean matrix, E the identity matrix, and \epsilon
   with 0<\epsilon<1 a constant.  If for any subset S of {0,\ldots,n-1}
   the submatrix of M+E over S\times S has at least \epsilon card(S) of
   mutually different columns, then rank(M+E) \ge (\epsilon n)/(4+3\epsilon).