Skip to main content

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

Author(s): Braverman, Mark; Ellen, F; Oshman, R; Pitassi, T; Vaikuntanathan, V

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1hm3z
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorEllen, F-
dc.contributor.authorOshman, R-
dc.contributor.authorPitassi, T-
dc.contributor.authorVaikuntanathan, V-
dc.date.accessioned2018-07-20T15:09:20Z-
dc.date.available2018-07-20T15:09:20Z-
dc.date.issued2013-26-10en_US
dc.identifier.citationBraverman, M, Ellen, F, Oshman, R, Pitassi, T, Vaikuntanathan, V. (2013). A tight bound for set disjointness in the message-passing model. 668 - 677. doi:10.1109/FOCS.2013.77en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1hm3z-
dc.description.abstractIn 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.en_US
dc.format.extent668 - 677en_US
dc.language.isoen_USen_US
dc.relation.ispartofProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS2013en_US
dc.rightsAuthor's manuscripten_US
dc.titleA tight bound for set disjointness in the message-passing modelen_US
dc.typeConference Articleen_US
dc.identifier.doidoi:10.1109/FOCS.2013.77-
dc.date.eissued2013-12-19en_US
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
A tight bound for set disjointness in the message-passing model.pdf200.71 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.