M.Sc Student | Aharoni Eldar |
---|---|

Subject | Direct Sum Related Problems in Communication Complexity |

Department | Department of Computer Science |

Supervisor | Professor Eyal Kushilevitz |

Full Thesis text |

We study the direct-sum problem and relaxations of
it, in different models of communication complexity. We show positive results
for the direct-sum problem for *k*-party “Number On the Forehead” (NOF)
deterministic communication complexity, showing that the complexity of
computing a function *f *in this model, on *l* instances, may be
significantly cheaper than *l* times the complexity of computing *f*
on a single instance. Quite surprisingly, we show that this is the case for “most”
(boolean, *k*-argument) functions.

We generalize the NOF model in a new model, NOF_{G},
which offers a more general notion of which input is seen by which parties. We
formalize sufficient conditions on a NOF_{G} protocol *Q*, for a
single instance, which guarantees some communication complexity savings when
appropriately extending *Q* to work on *l* instances, in the NOF
model. We give specific examples to the uses of this method. We also perform a
similar task on the one way-myopic NOF model. In all cases, the tool that we
use is “multiplexing”: we combine messages sent in parallel executions of
protocols for a single instance, into a single message for the multi-instance
(direct-sum) case, by xoring them with each other.

Next, we define a relaxation of direct-sum, termed
APP operator, which requires solving *l* instances of a function, with at
most *d* mistakes. We study this operator within different models of
communication complexity (both two-party and multi-party), and give upper and
lower bounds on the communication complexity of specific and general functions.

Finally, we revisit the previously studied operator CHOOSE, and consider a variant of it, in the NOF model.