### Communication Lower Bounds Using Directional DerivativesCommunication Lower Bounds Using Directional Derivatives

Access Restriction
Subscribed

 Author Sherstov, Alexander A. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2014 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Set disjointness problem ♦ Directional derivatives ♦ Multiparty communication complexity ♦ Polynomial approximation ♦ Quantum communication complexity Abstract We study the set disjointness problem in the most powerful model of bounded-error communication, the $\textit{k}-party$ randomized number-on-the-forehead model. We show that set disjointness requires $Ω(√n/2^{k}k)$ bits of communication, where $\textit{n}$ is the size of the universe. Our lower bound generalizes to quantum communication, where it is essentially optimal. Proving this bound was a longstanding open problem even in restricted settings, such as one-way classical protocols with $\textit{k}=4$ parties [Wigderson 1997]. The proof contributes a novel technique for lower bounds on multiparty communication, based on directional derivatives of protocols over the reals. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2014-12-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 61 Issue Number 6 Page Count 71 Starting Page 1 Ending Page 71

#### Open content in new tab

Source: ACM Digital Library