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


Direct Sum Related Problems in Communication Complexity
event speaker icon
Eldar Aharoni, M.Sc. Thesis Seminar
event date icon
Thursday, 19.6.2014, 14:30
event location icon
Taub 601
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.
[Back to the index of events]