Hazan, Itay ;
Kushilevitz, Eyal
TwoParty DirectSum Questions Through the Lens of Multiparty Communication Complexity
Abstract
Directsum questions in (twoparty) communication complexity ask whether two parties, Alice and Bob, can compute the value of a function f on l inputs (x_1,y_1),...,(x_l,y_l) more efficiently than by applying the best protocol for f, independently on each input (x_i,y_i). In spite of significant efforts to understand these questions (under various communicationcomplexity measures), the general question is still far from being well understood.
In this paper, we offer a multiparty view of these questions: The directsum setting is just a twoplayer system with Alice having inputs x_1,...,x_l, Bob having inputs y_1,...,y_l and the desired output is f(x_1,y_1),...,f(x_l,y_l). The naive solution of solving the l problems independently, is modeled by a network with l (disconnected) pairs of players Alice i and Bob i, with inputs x_i,y_i respectively, and communication only within each pair. Then, we consider an intermediate ("star") model, where there is one Alice having l inputs x_1,...,x_l and l players Bob_1,...,Bob_l holding y_1,...,y_l, respectively (in fact, we consider few variants of this intermediate model, depending on whether communication between each Bob i and Alice is pointtopoint or whether we allow broadcast). Our goal is to get a better understanding of the relation between the two extreme models (i.e., of the twoparty directsum question). If, for instance, Alice and Bob can do better (for some complexity measure) than solving the l problems independently, we wish to understand what intermediate model already allows to do so (hereby understanding the "source" of such savings). If, on the other hand, we wish to prove that there is no better solution than solving the l problems independently, then our approach gives a way of breaking the task of proving such a statement into few (hopefully, easier) steps.
We present several results of both types. Namely, for certain complexity measures, communication problems f and certain pairs of models, we can show gaps between the complexity of solving f on l instances in the two models in question; while, for certain other complexity measures and pairs of models, we can show that such gaps do not exist (for any communication problem f). For example, we prove that if only pointtopoint communication is allowed in the intermediate "star" model, then significant savings are impossible in the publiccoin randomized setting. On the other hand, in the privatecoin randomized setting, if Alice is allowed to broadcast messages to all Bobs in the "star" network, then some savings are possible. While this approach does not lead yet to new results on the original twoparty directsum question, we believe that our work gives new insights on the alreadyknown directsum results, and may potentially lead to more such results in the future.
BibTeX  Entry
@InProceedings{hazan_et_al:LIPIcs:2017:7999,
author = {Itay Hazan and Eyal Kushilevitz},
title = {{TwoParty DirectSum Questions Through the Lens of Multiparty Communication Complexity}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {26:126:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770538},
ISSN = {18688969},
year = {2017},
volume = {91},
editor = {Andr{\'e}a W. Richa},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7999},
URN = {urn:nbn:de:0030drops79998},
doi = {10.4230/LIPIcs.DISC.2017.26},
annote = {Keywords: Communication Complexity, Direct Sum, Multiparty Communication}
}
2017
Keywords: 

Communication Complexity, Direct Sum, Multiparty Communication 
Seminar: 

31st International Symposium on Distributed Computing (DISC 2017)

Issue date: 

2017 
Date of publication: 

2017 