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

皆様，大分，御無沙汰してしまいました．申し訳ありません．さて，多少，
急ですが，田中さんの紹介で，以下のようなセミナーを開きます．是非，
ご参加下さい．

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

   題目: Multiplicative complexity, fractals, and applications to
         electronic commerce
   講演者：Rene Peralta (Yale University)

The multiplicative complexity of a function is the
number of AND gates necessary and sufficient to
compute it using the base (AND,XOR,NOT). A powerful class
of protocols in electronic commerce have communication
cost linearly proportional to the multiplicative complexity
of the functions involved. We will explain this relation
and then move on to our results on the complexity of
symmetric functions. We show that fractals (specifically,
Sierpinski's gasket) can be used to bound the complexity
of threshold and other important symmetric functions.
We conclude the talk by presenting some simple applications
and discussing open problems.

This is joint work with Joan Boyar.

以上