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


   日時  ：６月１２日（木） １６：００〜
   場所  ：東京工業大学 南３号館 ２階 Ｓ３２３講義室
   連絡先：03-5734-2688
           計算工学専攻 渡辺 治（南３号館 ９階 ９１８号室）

   ＊Complexity Seminar Homepage:
     http://watanabe-www.cs.titech.ac.jp/~watanabe/comp-semi/home.html
     （今までの発表の概要や論文などが掲載されています．）

   Title: Average Case Circuit Complexity
   By: R"udiger Reischuk

In contrast to machine models like Turing or random access machines, 
circuits are a static, but nonuniform computational model.
The internal information flow of a computation is fixed in advance,
independent of the actual input.
Therefore, the size and the depth are natural and simple measures
for circuits and provide a worst case measure.

We introduce a model where an internal gate is evaluated 
as soon as its result is determined by the already available inputs. 
This way, we obtain a dynamic notion of delay and an average case measure 
for the time complexity of circuits.

Tight upper and lower bounds can be obtained for the average case complexity of
several basic Boolean functions. We will also examine the asymptotic average
case complexity of the set of all n-ary Boolean functions.
In contrast to worst case analysis a simple counting argument does not work.
We prove that almost all Boolean function require at least n-log n-loglog n
expected time even for the uniform probability distribution.
On the other hand, there is significant subset of functions that can be
computed with a constant average delay.

Finally, we compare worst case and average case complexity for this 
nonuniform computational model..
It is shown that for each function that is not computable by circuits of depth 
less than d, the expected time complexity will be at least d-log n-log d
with respect to an explicitely defined probability distribution.