8
$\begingroup$

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

$\endgroup$

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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$? $\endgroup$
    – Turbo
    Dec 18, 2016 at 21:25
  • $\begingroup$ It is $\Theta(1)$ for any trivial function and it is $\Theta(n)$ for the identity ($EQ$), for example. $\endgroup$
    – domotorp
    Dec 19, 2016 at 9:40
  • $\begingroup$ what partition gives the least cc for $EQ$? $\endgroup$
    – Turbo
    Dec 19, 2016 at 9:48
  • 1
    $\begingroup$ When for every $i$ the same person gets $x_i$ and $y_i$, then each person can check the equality of their indices themselves. $\endgroup$
    – domotorp
    Dec 19, 2016 at 14:46
  • $\begingroup$ So for paritition complexity the communication matrix not just permutes. It could mutate into something totally different? $\endgroup$
    – Turbo
    Dec 20, 2016 at 1:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.