We retract this paper due to a mistake in the main proof.

We show that for a relation $f\subseteq \{0,1\}^n\times \mathcal{O}$ and a function $g:\{0,1\}^{m}\times \{0,1\}^{m} \rightarrow \{0,1\}$ (with $m= O(\log n)$),
$$\mathrm{R}_{1/3}(f\circ g^n) = \Omega\left(\mathrm{R}_{1/3}(f) \cdot \left(\log\frac{1}{\mathrm{disc}(M_g)} - O(\log n)\right)\right),$$
where $f\circ g^n$ represents the composition of $f$ and $g^n$, $M_g$ is the sign matrix for $g$, $\mathrm{disc}(M_g)$ is the discrepancy of $M_g$ under the uniform distribution and $\mathrm{R}_{1/3}(f)$ ($\mathrm{R}_{1/3}(f\circ g^n)$) denotes the randomized query complexity of $f$ (randomized communication complexity of $f\circ g^n$) with worst case error $\frac{1}{3}$.

In particular, this implies that for a relation $f\subseteq \{0,1\}^n\times \mathcal{O}$, $$\mathrm{R}_{1/3}(f\circ \mathrm{IP}_m^n) = \Omega\left(\mathrm{R}_{1/3}(f) \cdot m\right),$$ where $\mathrm{IP}_m:\{0,1\}^m\times \{0,1\}^m\rightarrow \{0,1\}$ is the Inner Product (modulo $2$) function and $m= O(\log(n))$.

Further elaboration on proofs.

We show that for a relation $f\subseteq \{0,1\}^n\times \mathcal{O}$ and a function $g:\{0,1\}^{m}\times \{0,1\}^{m} \rightarrow \{0,1\}$ (with $m= O(\log n)$),
$$\mathrm{R}_{1/3}(f\circ g^n) = \Omega\left(\mathrm{R}_{1/3}(f) \cdot \left(\log\frac{1}{\mathrm{disc}(M_g)} - O(\log n)\right)\right),$$
where $f\circ g^n$ represents the composition of $f$ and $g^n$, $M_g$ is the sign matrix for $g$, $\mathrm{disc}(M_g)$ is the discrepancy of $M_g$ under the uniform distribution and $\mathrm{R}_{1/3}(f)$ ($\mathrm{R}_{1/3}(f\circ g^n)$) denotes the randomized query complexity of $f$ (randomized communication complexity of $f\circ g^n$) with worst case error $\frac{1}{3}$.

In particular, this implies that for a relation $f\subseteq \{0,1\}^n\times \mathcal{O}$, $$\mathrm{R}_{1/3}(f\circ \mathrm{IP}_m^n) = \Omega\left(\mathrm{R}_{1/3}(f) \cdot m\right),$$ where $\mathrm{IP}_m:\{0,1\}^m\times \{0,1\}^m\rightarrow \{0,1\}$ is the Inner Product (modulo $2$) function and $m= O(\log(n))$.

Revised proof.

This paper has been withdrawn due to an incorrigible error.

We show that for any (partial) query function $f:\{0,1\}^n\rightarrow \{0,1\}$, the randomized communication complexity of $f$ composed with $\mathrm{Index}^n_m$ (with $m= \poly(n)$) is at least the randomized query complexity of $f$ times $\log n$. Here $\mathrm{Index}_m : [m] \times \{0,1\}^m \rightarrow \{0,1\}$ is defined as $\mathrm{Index}_m(x,y)= y_x$ (the $x$th bit of $y$).

Our proof follows on the lines of Raz and Mckenzie [RM99] (and its generalization due to [GPW15]), who showed a lifting theorem for deterministic query complexity to deterministic communication complexity. Our proof deviates from theirs in an important fashion that we consider partitions of rectangles into many sub-rectangles, as opposed to a particular sub-rectangle with desirable properties, as considered by Raz and McKenzie. As a consequence of our main result, some known separations between quantum and classical communication complexities follow from analogous separations in the query world.