Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-155 | 22nd November 2011 01:16

The NOF Multiparty Communication Complexity of Composed Functions



We study the $k$-party `number on the forehead' communication complexity of composed functions $f \circ \vec{g}$, where $f:\{0,1\}^n \to \{\pm 1\}$, $\vec{g} = (g_1,\ldots,g_n)$, $g_i : \{0,1\}^k \to \{0,1\}$ and for $(x_1,\ldots,x_k) \in (\{0,1\}^n)^k$, $f \circ \vec{g}(x_1,\ldots,x_k) = f(\ldots,g_i(x_{1,i},\ldots,x_{k,i}), \ldots)$. When $\vec{g} = (g,g,\ldots,g)$ we denote $f \circ \vec{g}$ by $f \circ g$. We show that there is an $O(\log^3 n)$ cost simultaneous protocol for $\text{Sym} \circ g$ when $k > 1+\log n$, $\text{Sym}$ is any symmetric function and $g$ is any function. When $k > 1 + 2 \log n$, our simultaneous protocol applies to $\text{Sym} \circ \vec{g}$ with $\vec{g}$ being a vector of any $n$ functions. We also get a non-simultaneous protocol for $\text{Sym} \circ \vec{g}$ of cost $O(n/2^k \cdot \log n+ k \log n)$ for any $k \geq 2$. In the setting of $k \leq 1+\log n$ we study more closely functions of the form $\text{Majority} \circ g$, $\text{Mod}_m \circ g$, and $\text{Nor} \circ g$, where the latter two are generalizations of the well-known and studied functions Generalized Inner Product and Disjointness respectively. We characterize the communication complexity of these functions with respect to the choice of $g$. In doing so, we answer a question posed by Babai et al. (SIAM Journal on Computing, 33:137--166, 2003) and determine the communication complexity of $\text{Majority} \circ \text{Qcsb}_k$, where $\text{Qcsb}_k$ is the ``quadratic character of the sum of the bits'' function.

In the second part of our paper we utilize the connection between the 'number on the forehead' model and Ramsey theory to construct a large set without a $k$-dimensional corner ($k$-dimensional generalization of a $k$-term arithmetic progression) in $(\mathbb{F}_2^n)^k$, thereby obtaining the first non-trivial bound on the corresponding Ramsey number. Furthermore, we give an explicit coloring of $[N] \times [N]$ without a monochromatic 2-dimensional corner and use this to obtain an explicit 3-party protocol of cost $O(\sqrt{n})$ for the $\text{Exact}_N$ function. For $x_1,x_2,x_3$ $n$-bit integers, $\text{Exact}_N(x_1,x_2,x_3) = -1$ iff $x_1 + x_2 + x_3 = N$.

ISSN 1433-8092 | Imprint