אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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.