The Taub Faculty of Computer Science Events and Talks

We study the direct-sum problem for $k$-party ``Number On the Forehead'' (NOF) deterministic communication complexity. We prove several positive results, showing that the complexity of computing a function $f$ in this model, on $\ell$ instances, may be significantly cheaper than $\ell$ 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 then formalize sufficient conditions on a NOF protocol $Q$, for a single instance, which guarantees some communication complexity savings when appropriately extending $Q$ to work on $\ell$ instances. The conditions refer to what each party needs to know about inputs of the other parties. 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.