1
$\begingroup$

I'm looking for references about the behavior of communication complexity under input transformations. A specific toy example of the kind of question I'm interested in is the following.

Let $f(x_1,...,x_n)$ be a Boolean function over variables $\{x_1,...,x_n\}$ and $g(y_1,...,y_n,z_1,...,z_n)$ be a Boolean function over variables $\{y_1,...,y_n\} \cup \{z_1,....,z_n\}$ such that for each $a_1,...,a_n\in \{0,1\}^n$, $$f(a_1,...,a_n) = 1$$ if and only if there exists $b_1,...,b_n\in \{0,1\}^n$ and $c_1,...,c_n\in \{0,1\}^n$ such that $$g(b_1,...,b_n,c_1,...,c_n)=1 \mbox{ and } a_i = b_i \vee c_i \mbox{ for each $i\in \{1,...,n\}$}$$.

Question: Assume that the best partition communication complexity of $f$ is $d$. Is it true that the best partition communication complexity of $g$ is at least $d$?

$\endgroup$
  • 1
    $\begingroup$ A protocol for $g$ in particular has to work when all the $z_i$ variables are $0$, in which case you get a protocol for $f$. $\endgroup$ – Emil Jeřábek Jun 10 at 8:05
  • $\begingroup$ @EmilJeřábek I had asked the question in the wrong way. I have corrected the question now. $\endgroup$ – verifying Jun 10 at 10:17
  • $\begingroup$ Have you tried simple examples? E.g., $f=\textsf{AND}_n$, $g=\textsf{AND}_{2n}$ while setting $c_2=...=c_n=1$ and $c_1=f(a_1,...,a_n)$ for all $(a_i)_i$. $\endgroup$ – Clement C. Jun 10 at 14:58
  • $\begingroup$ Do you know this paper? eccc.weizmann.ac.il//report/2012/131 Especially Section 2 could be relevant, which suggests that the answer to your question is yes (at least with $\Omega(d)$). Without such methods, proving lower bounds for compositions is hard in CC. $\endgroup$ – domotorp Jun 13 at 5:38
  • $\begingroup$ Also see the later paper eccc.weizmann.ac.il/report/2012/171. $\endgroup$ – domotorp Jun 13 at 5:40

Your Answer

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

Browse other questions tagged or ask your own question.