Average Case Complexity of Unbounded Fanin Circuits

Hastad has shown that functions like PARITY cannot be computed by unbounded fanin circuits of small depth and polynomial size. We generalize this result in two directions. First, we obtain the same tight lower bound for the average case. This is done by estimating the average delay -- the natural generalization of circuit depth to an average case measure -- of unbounded fanin circuits of polynomial size, resp. their error probability given an upper bound on the maximal delay. These bounds are obtained by extending the probabilistic restriction method to an average case setting. Secondly, we completely classify the set of parallel prefix functions -- for which PARITY is just one example -- with respect to their average delay in unbounded fanin circuits of a given size. It is shown that only two cases can occur: a parallel prefix functions either has the same complexity as PARITY, that is the average delay has to be of order \Theta(log n= log log s) for circuit of size s , or it can be c..