Thumbnail
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

   Open content in new tab
Source: ACM Digital Library