A rounds vs. communication tradeoff for multi-party set disjointness

Mark Braverman, Rotem Oshman

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

4 Scopus citations

Abstract

In the set disjointess problem, we have k players, each with a private input X^i [n], and the goal is for the players to determine whether or not their sets have a global intersection. The players communicate over a shared blackboard, and we charge them for each bit that they write on the board.We study the trade-off between the number of interaction rounds we allow the players, and the total number of bits they must send to solve set disjointness. We show that if R rounds of interaction are allowed, the communication cost is (nk^{1/R}/R^4), which is nearly tight. We also leverage our proof to show that wellfare maximization with unit demand bidders cannot be solved efficiently in a small number of rounds: Here, we have k players bidding on n items, and the goal is to find a matching between items and player that bid on them which approximately maximizes the total number of items assigned. It was previously shown by Alon et. al. that (log log k) rounds of interaction are required to find an assignment which achieves a constant approximation to the maximum-wellfare assignment, even if each player is allowed to write n^{ϵ (R)} bits on the board in each round, where ϵ (R) = exp(-R). We improve this lower bound to log k / log log k), which is known to be tight up to a log log k factor.

Original languageEnglish (US)
Title of host publicationProceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017
PublisherIEEE Computer Society
Pages144-155
Number of pages12
ISBN (Electronic)9781538634646
DOIs
StatePublished - Nov 10 2017
Event58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017 - Berkeley, United States
Duration: Oct 15 2017Oct 17 2017

Publication series

NameAnnual Symposium on Foundations of Computer Science - Proceedings
Volume2017-October
ISSN (Print)0272-5428

Other

Other58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017
CountryUnited States
CityBerkeley
Period10/15/1710/17/17

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • maximum matching
  • round complxity
  • set disjointness

Fingerprint Dive into the research topics of 'A rounds vs. communication tradeoff for multi-party set disjointness'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., & Oshman, R. (2017). A rounds vs. communication tradeoff for multi-party set disjointness. In Proceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017 (pp. 144-155). [8104054] (Annual Symposium on Foundations of Computer Science - Proceedings; Vol. 2017-October). IEEE Computer Society. https://doi.org/10.1109/FOCS.2017.22