Communication Lower Bounds Using Directional Derivatives
Alexander A. Sherstov · Journal of the ACM · 2014
We study the set disjointness problem in the most powerful model of bounded-error communication, the k -party randomized number-on-the-forehead model. We show that set disjointness requires Ω(√n/2 k k ) bits of communication, where 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 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.