TY - GEN

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

AU - Braverman, Mark

AU - Oshman, Rotem

PY - 2017/11/10

Y1 - 2017/11/10

N2 - 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.

AB - 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.

KW - maximum matching

KW - round complxity

KW - set disjointness

UR - http://www.scopus.com/inward/record.url?scp=85041130523&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041130523&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2017.22

DO - 10.1109/FOCS.2017.22

M3 - Conference contribution

AN - SCOPUS:85041130523

T3 - Annual Symposium on Foundations of Computer Science - Proceedings

SP - 144

EP - 155

BT - Proceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017

PB - IEEE Computer Society

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

Y2 - 15 October 2017 through 17 October 2017

ER -