<p>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.</p>

CC BY-SA 3.0
2016-12-18T21:25:02.473Z
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
CC BY-SA 3.0
2016-12-19T09:40:24.620Z
It is $\Theta(1)$ for any trivial function and it is $\Theta(n)$ for the identity ($EQ$), for example.
domotorp
CC BY-SA 3.0
2016-12-19T09:48:28.110Z
what partition gives the least cc for $EQ$?
Turbo
CC BY-SA 3.0
2016-12-19T14:46:42.580Z
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
CC BY-SA 3.0
2016-12-20T01:01:08.477Z
So for paritition complexity the communication matrix not just permutes. It could mutate into something totally different?
Turbo
CC BY-SA 3.0
2016-12-20T08:39:33.443Z
Yes, you can put it that way.
domotorp
CC BY-SA 3.0
2016-12-18T12:22:16.660Z
2016-12-18T12:22:16.660Z
domotorp
<p>Let Alice and Bob compute boolean function $f(x_1,\dots,x_{2n})$.</p>

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

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

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

<p>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)$$</p>

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

<p>Is the related concepts introduced and studied anywhere?</p>

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

<reference-request><communication-complexity>
Is there a name for this concept in Communication Complexity?
Turbo
# Is there a name for this concept in Communication Complexity?

(Asked by: username_0 on 2016-12-18)

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$.

**Tags:** reference-request, communication-complexity

---

## 1 answers

### Answer by username_1 on 2016-12-18. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: 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$?  
> **username_1**: It is $\Theta(1)$ for any trivial function and it is $\Theta(n)$ for the identity ($EQ$), for example.  
> **username_0**: what partition gives the least cc for $EQ$?  
> **username_1**: When for every $i$ the same person gets $x_i$ and $y_i$, then each person can check the equality of their indices themselves.  
> **username_0**: So for paritition complexity the communication matrix not just permutes. It could mutate into something totally different?  
> **username_1**: Yes, you can put it that way.  

---

