דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Direct Sum Related Problems in Communication Complexity
event speaker icon
אלדר אהרוני, הרצאה סמינריונית למגיסטר
event date icon
יום חמישי, 19.6.2014, 14:30
event location icon
טאוב 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.
[בחזרה לאינדקס האירועים]