# How does Best Partition Communication Complexity behave under input transformations?

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

• 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 Jun 10 at 8:05
• @EmilJeřábek I had asked the question in the wrong way. I have corrected the question now. – verifying Jun 10 at 10:17
• 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. Jun 10 at 14:58
• 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. – domotorp Jun 13 at 5:38
• Also see the later paper eccc.weizmann.ac.il/report/2012/171. – domotorp Jun 13 at 5:40