TY - GEN
T1 - A tight bound for set disjointness in the message-passing model
AU - Braverman, Mark
AU - Ellen, Faith
AU - Oshman, Rotem
AU - Pitassi, Toniann
AU - Vaikuntanathan, Vinod
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84893499491&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893499491&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2013.77
DO - 10.1109/FOCS.2013.77
M3 - Conference contribution
AN - SCOPUS:84893499491
SN - 9780769551357
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 668
EP - 677
BT - Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
T2 - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Y2 - 27 October 2013 through 29 October 2013
ER -