×

Communication complexity of simultaneous messages. (English) Zbl 1069.68051

Summary: In the multiparty communication game (CFL game) of A. K. Chandra, M. L. Furst, and R. J. Lipton [Proc. 15th Annual ACM Symposium on Theory of Computing, Boston, MA, 94–99 (1983)], \(k\) players collaboratively evaluate a function \(f(x_{0},\dots,x_{k-1})\) in which player \(i\) knows all inputs except \(x^i\). The players have unlimited computational power. The objective is to minimize communication.
We study the Simultaneous Messages (SM) model of multiparty communication complexity. The SM model is a restricted version of the CFL game, in which the players are not allowed to communicate with each other. Instead, each of the \(k\) players simultaneously sends a message to a referee, who sees none of the inputs. The referee then announces the function value.
We prove lower and upper bounds on the SM complexity of several classes of explicit functions. Our lower bounds extend to randomized SM complexity via an entropy argument. A lemma establishing a tradeoff between average Hamming distance and range size for transformations of the Boolean cube might be of independent interest.
Our lower bounds on SM complexity imply an exponential gap between the SM model and the CFL model for up to \((\log n)^{1-\varepsilon}\) players for any \(\epsilon > 0\). This separation is obtained by comparing the respective complexities of the Generalized Addressing Function, \(\text{GAF}_{G,k}\), where \(G\) is a group of order \(n\). We also combine our lower bounds on SM complexity with the ideas of J. Håstad and M. Goldmann [Comput. Complexity 1, 113–129 (1991; Zbl 0774.68060)] to derive superpolynomial lower bounds for certain depth-2 circuits computing a function related to the GAF function.
We prove some counterintuitive upper bounds on SM complexity. We show that \(\text{GAF}_{\mathbb{Z}_2^t,3}\) has SM complexity \(O(n^{0.92})\). When the number of players is at least \(c\log n\), for some constant \(c>0\), our SM protocol for \(\text{GAF}_{\mathbb{Z}_2^t,k}\) has polylog(\(n\)) complexity. We also examine a class of functions defined by certain depth-2 circuits. This class includes the ‘Generalized Inner Product’ function and ‘Majority of Majorities’. When the number of players is at least \(2+\log n\), we obtain polylog(\(n\)) upper bounds for this class of functions.

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R05 Combinatorics in computer science

Citations:

Zbl 0774.68060
PDFBibTeX XMLCite
Full Text: DOI