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

<p>Let <span class="math-container">$f(x_1,...,x_n)$</span> be a Boolean function over variables <span class="math-container">$\{x_1,...,x_n\}$</span> and <span class="math-container">$g(y_1,...,y_n,z_1,...,z_n)$</span> be a Boolean function over variables <span class="math-container">$\{y_1,...,y_n\} \cup \{z_1,....,z_n\}$</span> such that for each <span class="math-container">$a_1,...,a_n\in \{0,1\}^n$</span>, 
<span class="math-container">$$f(a_1,...,a_n) = 1$$</span> if and only if there exists <span class="math-container">$b_1,...,b_n\in \{0,1\}^n$</span> and <span class="math-container">$c_1,...,c_n\in \{0,1\}^n$</span> such that 
<span class="math-container">$$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\}$}$$</span>. </p>

<p><strong>Question:</strong> Assume that the best partition communication complexity of <span class="math-container">$f$</span> is <span class="math-container">$d$</span>. Is it true that the
best partition communication complexity of <span class="math-container">$g$</span> is at least <span class="math-container">$d$</span>? </p>

CC BY-SA 4.0
2019-06-10T08:05:54.693Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2019-06-10T10:17:52.813Z
@EmilJeřábek I had asked the question in the wrong way. I have corrected the question now.
verifying
CC BY-SA 4.0
2019-06-10T14:58:36.207Z
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$.
Clement C.
CC BY-SA 4.0
2019-06-13T05:38:57.097Z
Do you know this paper? https://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.
domotorp
CC BY-SA 4.0
2019-06-13T05:40:35.817Z
Also see the later paper https://eccc.weizmann.ac.il/report/2012/171/.
domotorp
<communication-complexity>
How does Best Partition Communication Complexity behave under input transformations?
verifying
# How does Best Partition Communication Complexity behave under input transformations?

(Asked by: username_0 on 2019-06-10)

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

**Tags:** communication-complexity
> **Comments:**
> **username_1**: 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$.  
> **username_0**: @EmilJeřábek I had asked the question in the wrong way. I have corrected the question now.  
> **username_2**: 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$.  
> **username_3**: Do you know this paper? https://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.  
> **username_3**: Also see the later paper https://eccc.weizmann.ac.il/report/2012/171/.  

---

## 0 answers

