  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,?\}$ is permutation-invariant if for every bijection
$\pi:\{1,\ldots,n\} \to \{1,\ldots,n\}$ and every $\mathbf{x}, \mathbf{y} \in
\{0,1\}^n$, it is the case that $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.
