Technical Report MSC-2017-12

Title: Two-Party Direct-Sum Questions through the Lens of Multiparty Communication Complexity
Authors: Itay Hazan
Supervisors: Eyal Kushilevitz
PDFCurrently accessibly only within the Technion network
Abstract: The direct-sum question in two-party communication complexity is the following; Alice receives (x_1,…,x_ℓ) and Bob receives (y_1,…,y_ℓ), where each x_i and y_i are n-bit strings. Together, they wish to compute f(x_i,y_i) for every iϵ{1,…,ℓ}, where f is some predetermined function. A saving is said to occur if Alice and Bob can utilize the fact that they are given the ℓ instances simultaneously in order to compute the outputs f(x_i,y_i) more efficiently than solving each instance separately. We study the two-party direct-sum question by considering multiparty models, in which there are (ℓ+1) parties; one Alice and ℓ Bobs, to whom we refer as Bob1, …, Bobℓ. We define several such multiparty models, differentiated by the type of communication they allow, e.g. broadcast or point-to-point. In the models we suggest, Alice receives (x_1,…,x_ℓ) and each Bob_i receives y_i. The question becomes whether a saving can be obtained in a setting in which one party sees ℓ instances at once, and may send messages that are “global”, while each of the other parties sees only one instance and sends messages that rely solely on this instance and its view of the communication. We consider these questions under all standard communication complexity measures, i.e. deterministic, nondeterministic, and randomized, and demonstrate how our results relate to the hardness of classical two-party direct-sum questions. We prove that if only point-to-point communication is allowed in our (ℓ+1)-party setting, then a significant saving can be obtained neither in the public-coin randomized setting nor in the nondeterministic setting. However, we prove that if Alice is allowed to broadcast messages to all Bobs simultaneously in the nondeterministic setting, then it is possible to achieve any saving that can be obtained in the two-party nondeterministic direct-sum setting. We also examine functions for which savings are known to occur in the classical direct-sum setting and ask whether these savings can also be obtained in our (ℓ+1)-party model. We show, for example, that savings can be obtained for the equality function in the private-coin randomized (ℓ+1)-party model as long as at least one party is able to broadcast messages to all others. If the communication is point-to-point, however, then the parties cannot obtain any significant saving. We prove a similar result for the non-equality function in the nondeterministic setting. We also consider the direct-sum question in one-round protocols, in which Alice is not allowed to send messages to the Bobs. We provide an example in the private-coin randomized setting in which a significant saving can be obtained when the Bobs can hear each other’s messages, but cannot be obtained when they are forced to send independent messages. Contrary to the private-coin randomized setting, we prove that no saving can be obtained if only public-coin randomization is allowed, even if the Bobs can hear each other's communication.
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 2017
To the main CS technical reports page

Computer science department, Technion