A tight bound for set disjointness in the message-passing model

Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

42 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Pages668-677
Number of pages10
DOIs
StatePublished - Dec 1 2013
Event2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 - Berkeley, CA, United States
Duration: Oct 27 2013Oct 29 2013

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
CountryUnited States
CityBerkeley, CA
Period10/27/1310/29/13

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'A tight bound for set disjointness in the message-passing model'. Together they form a unique fingerprint.

Cite this