Malign Distributions for Average Case Circuit Complexity

In contrast to machine models like Turing machines or random access machines, circuits are a static 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 consider a model where an internal gate is evaluated as soon as its result is determined by the already available input. So we obtain a dynamic notion of delay. In [JRS94] we have defined an average case measure for the time complexity of circuits. Using this notion tight upper and lower bounds could be obtained for the average case complexity of several basic Boolean functions. Here, we will 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 \Gamma log n \Gamma llog n expected ti..