We consider the communication complexity of finding an approximate maximum matching in a graph in a multi-party message-passing communication model. The maximum matching problem is one of the most fundamental graph combinatorial problems, with a variety of applications. The input to the problem is a graph @math that has @math vertices and the set of edges partitioned over @math sites, and an approximation ratio parameter @math . The output is required to be a matching in @math that has to be reported by one of the sites, whose size is at least factor @math of the size of a maximum matching in @math . We show that the communication complexity of this problem is @math information bits. This bound is shown to be tight up to a @math factor, by constructing an algorithm, establishing its correctness, and an upper bound on the communication cost. The lower bound also applies to other graph combinatorial problems in the message-passing communication model, including max-flow and graph sparsification.
In @cite_2 , it has been shown that the communication complexity of the problem in the message-passing model is @math bits. This work was independent and concurrent to ours. Incidentally, it uses a similar but different input distribution to ours. Similar input distributions were also used in previous work such as @cite_11 and @cite_13 . This is not surprising because of the nature of the message-passing model. There may exist a reduction between the @math -party set-disjointness and , but showing this is non-trivial and would require a formal proof. The proof of our lower bound is different in that we use a reduction of the @math -party to a @math -party set-disjointness using a symmetrisation argument, while @cite_2 uses a coordinative-wise direct-sum theorem to reduce the @math -party set-disjointness to a @math -party @math -bit problem.
@cite_11 @cite_13 @cite_2
2568405002 2950318219 2085382249
In this paper we prove lower bounds on randomized multiparty communication complexity, mainly in the message-passing model, where messages are sent player-to-player. Some of our results apply to the blackboard model, where each message is written on a blackboard for all players to see. We introduce a new technique for proving such bounds, called symmetrization, which is natural, intuitive, and often easy to use. For example, for the problem where each of @math players gets a bit-vector of length @math , and the goal is to compute the coordinatewise XOR of these vectors, we prove a tight lower bound of @math in the blackboard model. For the same problem with AND instead of XOR, we prove a lower bound of roughly @math in the message-passing model (assuming @math ) and @math in the blackboard model. We also prove lower bounds for bitwise majority, for a graph-connectivity problem, and for other problems; the technique seems applicable to a wide range of other problems as well. A... We resolve several fundamental questions in the area of distributed functional monitoring, initiated by Cormode, Muthukrishnan, and Yi (SODA, 2008). In this model there are @math sites each tracking their input and communicating with a central coordinator that continuously maintain an approximate output to a function @math computed over the union of the inputs. The goal is to minimize the communication. We show the randomized communication complexity of estimating the number of distinct elements up to a @math factor is @math , improving the previous @math bound and matching known upper bounds up to a logarithmic factor. For the @math -th frequency moment @math , @math , we improve the previous @math communication bound to @math . We obtain similar improvements for heavy hitters, empirical entropy, and other problems. We also show that we can estimate @math , for any @math , using @math communication. This greatly improves upon the previous @math bound of Cormode, Muthukrishnan, and Yi for general @math , and their @math bound for @math . For @math , our bound resolves their main open question. Our lower bounds are based on new direct sum theorems for approximate majority, and yield significant improvements to problems in the data stream model, improving the bound for estimating @math in @math passes from @math to @math , giving the first bound for estimating @math in @math passes of @math bits of space that does not use the gap-hamming problem. In a multiparty message-passing model of communication, there are k players. Each player has a private input, and they communicate by sending messages to one another over private channels. While this model has been used extensively in distributed computing and in secure multiparty computation, lower bounds on communication complexity in this model and related models have been somewhat scarce. In recent work [25], [29], [30], strong lower bounds of the form Ω(n·k) were obtained for several functions in the message-passing model; however, a lower bound on the classical set disjointness problem remained elusive. In this paper, we prove a tight lower bound of Ω(n · k) for the set disjointness problem in the message passing model. Our bound is obtained by developing information complexity tools for the message-passing model and proving an information complexity lower bound for set disjointness.