Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Events

Events

Two-Party Direct-Sum Questions through the Lens of Multiparty Communication Complexity
event speaker icon
Itay Hazan, M.Sc. Thesis Seminar
event date icon
Monday, 13.2.2017, 13:00
event location icon
Taub 337
The direct-sum question in two-party communication complexity is the following; Alice receives $(x_1,\dots,x_\ell)$ and Bob receives $ (y_1,\dots,y_\ell) $, where each $x_i$ and $y_i$ are $n$-bit strings. Together, they wish to compute $f(x_i,y_i)$ for every $ i \in \{1,\dots,\ell\}$, where $f$ is some predetermined function. A \emph{saving} is said to occur if Alice and Bob can utilize the fact that they are given the $\ell$ 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 $(\ell+1)$ parties; one Alice and $\ell$ Bobs, to whom we refer as $ Bob_1, \dots, Bob_\ell $. 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, the question becomes whether a saving can be obtained in a setting in which one party sees $\ell$ 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 prove connections between the models with respect to various complexity measures, i.e. deterministic, nondeterministic, and randomized, and demonstrate how our results relate to the hardness of classical two-party direct-sum questions.
[Back to the index of events]