Abstract
In a kparty communication problem, the k players with inputs x_1, x_2, ..., x_k, respectively, want to evaluate a function f(x_1, x_2, ..., x_k) using as little communication as possible. We consider the messagepassing model, in which the inputs are partitioned in an arbitrary, possibly worstcase manner, among a smaller number t of players (t<k). The tplayer communication cost of computing f can only be smaller than the kplayer communication cost, since the t players can trivially simulate the kplayer protocol. But how much smaller can it be? We study deterministic and randomized protocols in the oneway model, and provide separations for product input distributions, which are optimal for low error probability protocols. We also provide much stronger separations when the input distribution is nonproduct.
A key application of our results is in proving lower bounds for data stream algorithms. In particular, we give an optimal Omega(epsilon^{2}log(N) log log(mM)) bits of space lower bound for the fundamental problem of (1 +/{epsilon})approximating the number x _0 of nonzero entries of an ndimensional vector x after m updates each of magnitude M, and with success probability >= 2/3, in a strict turnstile stream. Our result matches the best known upper bound when epsilon >= 1/polylog(mM). It also improves on the prior Omega({epsilon}^{2}log(mM)) lower bound and separates the complexity of approximating L_0 from approximating the pnorm L_p for p bounded away from 0, since the latter has an O(epsilon^{2}log(mM)) bit upper bound.
BibTeX  Entry
@InProceedings{woodruff_et_al:LIPIcs:2019:10673,
author = {David P. Woodruff and Guang Yang},
title = {{Separating kPlayer from tPlayer OneWay Communication, with Applications to Data Streams}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {97:197:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10673},
URN = {urn:nbn:de:0030drops106733},
doi = {10.4230/LIPIcs.ICALP.2019.97},
annote = {Keywords: Communication complexity, multiplayer communication, oneway communication, streaming complexity}
}
Keywords: 

Communication complexity, multiplayer communication, oneway communication, streaming complexity 
Collection: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) 
Issue Date: 

2019 
Date of publication: 

04.07.2019 