### 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 language | English (US) |
---|---|

Title of host publication | Proceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017 |

Publisher | IEEE Computer Society |

Pages | 144-155 |

Number of pages | 12 |

ISBN (Electronic) | 9781538634646 |

DOIs | |

State | Published - Nov 10 2017 |

Event | 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017 - Berkeley, United States Duration: Oct 15 2017 → Oct 17 2017 |

### Publication series

Name | Annual Symposium on Foundations of Computer Science - Proceedings |
---|---|

Volume | 2017-October |

ISSN (Print) | 0272-5428 |

### Other

Other | 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017 |
---|---|

Country | United States |

City | Berkeley |

Period | 10/15/17 → 10/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

*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