AVERAGE AND RANDOMIZED COMPLEXITY OF DISTRIBUTED PROBLEMS

Yao proved that in the decision-tree model, the average complexity of the best deterministic algorithm is a lower bound on the complexity of randomized algorithms that solve the same problem. Here it is shown t hat a similar result does not always hold in the common model of distr ibuted computation, the model in which all the processors run the same program (which may depend on the processors' input). We therefore con struct a new technique that together with Yao's method enables us to s how that in many cases, a similar relationship does hold in the distri buted model. This relationship enables us to carry over known lower bo unds an the complexity of deterministic computations to the realm of r andomized computations, thus obtaining new results. The new technique can also be used for obtaining results concerning algorithms with boun ded error.