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

The Taub Faculty of Computer Science Events and Talks

Direct Sum Related Problems in Communication Complexity
event speaker icon
Eldar Aharoni (M.Sc. Thesis Seminar)
event date icon
Thursday, 19.06.2014, 14:30
event location icon
Taub 601
event speaker icon
Advisor: Prof. E. Kushilevitz
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.