Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > IMPERFECTLY SHARED RANDOMNESS:
Reports tagged with Imperfectly Shared Randomness:
TR15-087 | 30th May 2015

#### 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,?\}$ 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}) ... more >>>

TR17-081 | 2nd May 2017