Communication Complexity of Permutation-Invariant Functions

Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of “permutation-invariant” functions. A partial function $f:{0,1}^n \times {0,1}^n\to {0,1,?}$ispermutation-invariantifforeverybijection$\pi:{1,\ldots,n} \to {1,\ldots,n}$andevery$$\mathbf{x}$, $\mathbf{y}$ \in {0,1}^n$,itisthecasethat$f($\mathbf{x}$, $\mathbf{y}$) = f($\mathbf{x}$^{\pi}, $\mathbf{y}$^{\pi})$. Most of the commonly studied functions in communication complexity are permutation-invariant. For such functions, we present a simple complexity measure (computable in time polynomial in $n$ given an implicit description of $f$) that describes their communication complexity up to polynomial factors and up to an additive error that is logarithmic in the input size. This gives a coarse taxonomy of the communication complexity of simple functions. Our work highlights the role of the well-known lower bounds of functions such as ‘Set-Disjointness’ and ‘Indexing’, while complementing them with the relatively lesser-known upper bounds for ‘Gap-Inner-Product’ (from the sketching literature) and ‘Sparse-Gap-Inner-Product’ (from the recent work of Canonne et al. [ITCS 2015]). We also present consequences to the study of communication complexity with imperfectly shared randomness where we show that for total permutation-invariant functions, imperfectly shared randomness results in only a polynomial blow-up in communication complexity after an additive $O(\log \log n)$ overhead.