Technical Report MSC-2015-01

Title: Direct Sum Related Problems in Communication Complexity
Authors: Eldar Aharoni
Supervisors: Eyal Kushilevitz
PDFCurrently accessibly only within the Technion network
Abstract: We study the direct-sum problem and relaxations of it, in different models of communication complexity. We show positive results for the direct-sum problem for k-party “Number On the Forehead” (NOF) deterministic communication complexity, showing that the complexity of computing a function f in this model, on l instances, may be significantly cheaper than l times the complexity of computing f on a single instance. Quite surprisingly, we show that this is the case for “most” (boolean, k-argument) functions.

We generalize the NOF model in a new model, NOF_G, which offers a more general notion of which input is seen by which parties. We formalize sufficient conditions on a NOF_G protocol Q, for a single instance, which guarantees some communication complexity savings when appropriately extending Q to work on l instances, in the NOF model. We give specific examples to the uses of this method. We also perform a similar task on the one way-myopic NOF model. In all cases, the tool that we use is “multiplexing”: we combine messages sent in parallel executions of protocols for a single instance, into a single message for the multi-instance (direct-sum) case, by xoring them with each other.

Next, we define a relaxation of direct-sum, termed APP operator, which requires solving l instances of a function, with at most d mistakes. We study this operator within different models of communication complexity (both two-party and multi-party), and give upper and lower bounds on the communication complexity of specific and general functions. Finally, we revisit the previously studied operator CHOOSE, and consider a variant of it, in the NOF model.

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 (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2015
To the main CS technical reports page

Computer science department, Technion