Loading [MathJax]/jax/element/mml/optable/GeneralPunctuation.js
pdf icon
Volume 19 (2023) Article 10 pp. 1-44
Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams
Received: September 25, 2021
Revised: January 8, 2023
Published: December 31, 2023
Download article from ToC site:
[PDF (505K)] [PS (2903K)] [Source ZIP]
Keywords: streaming, space complexity, Hamming norm, approximation, algorithms with predictions, direct sum
ACM Classification: F.1.3, F.2.3, F.2.1
AMS Classification: 68Q17, 68W25, 68W20

Abstract: [Plain Text Version]

In a k-party communication problem, the k players with inputs x1,x2,,xk want to evaluate a function f(x1,x2,,xk) using as little communication as possible. We consider the message-passing model, in which the inputs are partitioned in an arbitrary, possibly worst-case manner, among a smaller number t of players (t<k). The t-player communication cost of computing f can only be smaller than the k-player communication cost, since the t players can trivially simulate the k-player protocol. But how much smaller can it be? We study deterministic and randomized protocols in the one-way 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 non-product.

A key application of our results is in proving lower bounds for data stream algorithms. In particular, we give an optimal Ω(ε2log(N)loglog(mM)) bits of space lower bound for the fundamental problem of (1±ε)-approximating the number of non-zero entries of an n-dimensional vector x after m integer updates each of magnitude at most M, and with success probability \ge 2/3, in a strict turnstile stream. We additionally prove the matching \Omega(\gap^{-2}\log(N) \log \log(T)) space lower bound for the problem when we have access to a heavy hitters oracle with threshold T. Our results match the best known upper bounds when \gap\ge 1/\polylog(mM) and when T = 2^{\poly(1/\epsilon)}, respectively. It also improves on the prior \Omega(\gap^{-2}\log(mM) ) lower bound and separates the complexity of approximating L_0 from approximating the p-norm L_p for p bounded away from 0, since the latter has an O(\gap^{-2}\log (mM)) bit upper bound.

--------------------------

A preliminary version of this paper, by a subset of the authors, appeared in the Proceedings of the 46th International Colloquium on Automata, Languages and Programming, 2019 (ICALP'19).