Technical Report CS0765

TR#:CS0765
Class:CS
Title: AVERAGE AND RANDOMIZED COMPLEXITY OF DISTRIBUTED PROBLEMS.
Authors: N. Allenberg-Navony, A. Itai and S. Moran
PDFCS0765.pdf
Abstract:

A.C. 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 that this result does not always hold in the common model of distributed computation, the model in which all the processors run the same program (that may depend on the processors' input). We, therefore, construct a new technique that extends Yao's method and enables us to show that in some cases a similar relationship does hold in the distributed model. This relationship enables us to carry over known lower bounds on the complexity of deterministic computations to the randomized computations, thus obtaining new results. The new technique can also be used for obtaining results concerning algorithms with bounded error.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1993/CS/CS0765), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1993
To the main CS technical reports page

Computer science department, Technion
admin