Title: Tight Bounds for Set Disjointness in the Message-Passing Model
Speaker: Rotem Oshman, Princeton University/Tel Aviv University
Date: Wednesday, September 18, 2013 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In many distributed systems, the cost of computation is dominated by the cost of communication between the machines participating in the computation. Communication complexity is therefore a very useful tool in understanding distributed computation, and communication complexity lower bounds have been used extensively to obtain lower bounds on various distributed problems. However, almost all applications of communication complexity lower bounds in distributed computing use two-party lower bounds, despite the fact that distributed computation usually involves many players. Unfortunately, there are interesting distributed problems that it appears cannot be addressed using two-player lower bounds, because reductions from two-player problems seem to lose the "hardness" of the problem.
With this motivation in mind, in this work we study communication complexity in the multi-party message-passing model, which has been extensively used in distributed computing and in secure multi-party computation. In the message-passing model there are k players, each with a private n-bit input, and the players communicate with each other over private channels. We show a lower bound of Omega(n*k) on the communication complexity of set disjointness in the message-passing model. To obtain this bound we develop information complexity tools for the model, prove a direct-sum theorem, and show that the information complexity of computing a 1-bit AND with k players is Omega(k).
This is joint work with Mark Braverman, Faith Ellen, Toniann Pitassi and Vinod Vaikuntanathan.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/F13/