# Is there a name for this concept in Communication Complexity?

Let Alice and Bob compute boolean function $f(x_1,\dots,x_{2n})$.

Select a random subset $\mathcal I\subseteq\{1,\dots,2n\}$ of cardinality $n$ and let $\mathcal J=\{1,\dots,2n\}\backslash\mathcal I$.

Let Alice get variables $x_i$ where $i\in\mathcal I$ and Bob get $x_j$ where $j\in\mathcal J$.

Let communication complexity of this function under this partition be $CC_{\mathcal I,\mathcal J}(f)$

Define $$cc_{min}(f)=\min_{\substack{\mathcal I\subseteq\{1,\dots,2n\}\\\mathcal J=\{1,\dots,2n\}\backslash\mathcal I\\|\mathcal I|=|\mathcal J|=n}}CC_{\mathcal I,\mathcal J}(f)$$ $$cc_{max}(f)=\max_{\substack{\mathcal I\subseteq\{1,\dots,2n\}\\\mathcal J=\{1,\dots,2n\}\backslash\mathcal I\\|\mathcal I|=|\mathcal J|=n}}CC_{\mathcal I,\mathcal J}(f)$$

Is there a term for $cc_{max}(f)-cc_{min}(f)$ and $\frac{cc_{max}(f)}{cc_{min}(f)}$?

Is the related concepts introduced and studied anywhere?

I am also interested in scenarios where $|\mathcal I|\neq\mathcal J|$ under condition $||\mathcal I|-\mathcal J||\leq \log n$.

What you call $cc_{max}$ is known as the worst-case partition communication complexity, and what you call $cc_{min}$ is known as the best-case partition communication complexity. These have been studied for several functions, you can find some results in the book of Kushilevitz and Nisan in chapter 7. I'm not aware of anyone introducing the difference or the ratio as a parameter to study.
• Is there a class of $f$ for which the ratio is close to $1$ and a class of $f$ for which the ratio is close $n$? – Turbo Dec 18 '16 at 21:25
• It is $\Theta(1)$ for any trivial function and it is $\Theta(n)$ for the identity ($EQ$), for example. – domotorp Dec 19 '16 at 9:40
• what partition gives the least cc for $EQ$? – Turbo Dec 19 '16 at 9:48
• When for every $i$ the same person gets $x_i$ and $y_i$, then each person can check the equality of their indices themselves. – domotorp Dec 19 '16 at 14:46