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

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
אלדר אהרוני (הרצאה סמינריונית למגיסטר)
event date icon
יום חמישי, 19.06.2014, 14:30
event location icon
Taub 601
event speaker icon
מנחה: 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.