About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SODA 2014
Conference paper
An optimal lower bound for distinct elements in the message passing model
Abstract
In the message-passing model of communication, there are k players each with their own private input, who try to compute or approximate a function of their inputs by sending messages to one another over private channels. We consider the setting in which each player holds a subset Si of elements of a universe of size n, and their goal is to output a (1 + ε)-approximation to the total number of distinct elements in the union of the sets Si with constant probability, which can be amplified by independent repetition. This problem has applications in data mining, sensor networks, and network monitoring. We resolve the communication complexity of this problem up to a constant factor, for all settings of n, k and ε, by showing a lower bound of Ω(k ·; min(n, 1/ε2) + klogn) bits. This improves upon previous results, which either had non-trivial restrictions on the relationships between the values of n, k, and ε, or were suboptimal by logarithmic factors, or both. Copyright © 2014 by the Society for Industrial and Applied Mathematics.