טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentHazan Itay
SubjectTwo-Party Direct-Sum Questions through the Lens of
Multiparty Communication Complexity
DepartmentDepartment of Computer Science
Supervisor Professor Eyal Kushilevitz
Full Thesis textFull thesis text - English Version


Abstract

The direct-sum question in two-party communication complexity is the following; Alice receives (x1,?,x?) and Bob receives (y1,?,y), where each xi and yi are n-bit strings. Together, they wish to compute f(xi,yi) 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(xi,yi) more efficiently than solving each instance separately.

We study the two-party direct-sum question by considering multiparty models, in which there are (ℓ) 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 (x1,?,x) and each Bobi receives yi. 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 (ℓ)-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 (ℓ)-party model. We show, for example, that savings can be obtained for the equality function in the private-coin randomized (ℓ)-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.