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$
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$
  • $\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$ – T.... Dec 18 '16 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 '16 at 9:40
  • $\begingroup$ what partition gives the least cc for $EQ$? $\endgroup$ – T.... Dec 19 '16 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 '16 at 14:46
  • $\begingroup$ So for paritition complexity the communication matrix not just permutes. It could mutate into something totally different? $\endgroup$ – T.... Dec 20 '16 at 1:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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