M.Sc Student | Hazan Itay |
---|---|

Subject | Two-Party Direct-Sum Questions through the Lens of Multiparty Communication Complexity |

Department | Department of Computer Science |

Supervisor | Professor Eyal Kushilevitz |

Full Thesis text |

The direct-sum question in two-party communication complexity
is the following; Alice receives *(x _{1},?,x?_{ℓ})*
and Bob receives

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 Bob_{1}, ?, 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

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.