Vinod Vaikuntanathan: Tools in Multiparty Communication Complexity, and a lower-bound for Set Disjointness

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 multiparty computation, lower bounds on communication complexity
in this model and related models have been somewhat scarce.

I will present a tight lower bound of the form $\Omega(n \cdot k)$ for
the Set Disjointness problem in the message passing model. Our
bound is obtained by developing information complexity tools in the
message-passing model. As a corollary, we obtain a tight lower
bound for the task allocation problem.

Joint work with Mark Braverman, Faith Ellen, Rotem Oshman and Toni Pitassi.