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
2951592515 2073639613 2085382249 2568405002
This paper provides the first general technique for proving information lower bounds on two-party unbounded-rounds communication problems. We show that the discrepancy lower bound, which applies to randomized communication complexity, also applies to information complexity. More precisely, if the discrepancy of a two-party function @math with respect to a distribution @math is @math , then any two party randomized protocol computing @math must reveal at least @math bits of information to the participants. As a corollary, we obtain that any two-party protocol for computing a random function on @math must reveal @math bits of information to the participants. In addition, we prove that the discrepancy of the Greater-Than function is @math , which provides an alternative proof to the recent proof of Viola Viola11 of the @math lower bound on the communication complexity of this well-studied function and, combined with our main result, proves the tight @math lower bound on its information complexity. The proof of our main result develops a new simulation procedure that may be of an independent interest. In a very recent breakthrough work of kerenidis2012lower , this simulation procedure was the main building block for proving that almost all known lower bound techniques for communication complexity (and not just discrepancy) apply to information complexity. We describe new ways to simulate two-party communication protocols to get protocols with potentially less communication. We show that every communication protocol that communicates @math bits and reveals @math bits of information about the inputs to the participating parties can be simulated by a new protocol involving at most @math bits of communication. If the protocol reveals @math bits of information about the inputs to an observer that watches the communication in the protocol, we show how to carry out the simulation with @math bits of communication. These results lead to a direct sum theorem for randomized communication complexity. Ignoring polylogarithmic factors, we show that for worst-case computation, computing @math copies of a function requires @math times the communication required for computing one copy of the function. For average case complexity, given any distribution @math on inputs, computing @math copies of the function on @math inputs sampled independently according... 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. 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...