In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions $f$ composed with the Inner Product gadget $g_{IP}(x,y) = \sum_i x_iy_i \mathrm{mod} \, 2$ of logarithmic size. In other words, given a function $f: ... more >>>

We prove a randomized communication-complexity lower bound for a composed OrderedSearch $\circ$ IP — by lifting the randomized query-complexity lower-bound of OrderedSearch to the communication-complexity setting. We do this by extending ideas from a paper of Raz and Wigderson. We think that the techniques we develop will be useful in ... more >>>

We show a deterministic simulation (or lifting) theorem for composed problems $f \circ EQ_n$ where the inner function (the gadget) is Equality on $n$ bits. When $f$ is a total function on $p$ bits, it is easy to show via a rank argument that the communication complexity of $f\circ EQ_n$ ... more >>>

Lifting theorems are theorems that relate the query complexity of a function $f:\left\{ 0,1 \right\}^n\to \left\{ 0,1 \right\}$ to the communication complexity of the composed function $f\circ g^n$, for some “gadget” $g:\left\{ 0,1 \right\}^b\times \left\{ 0,1 \right\}^b\to \left\{ 0,1 \right\}$. Such theorems allow transferring lower bounds from query complexity to ... more >>>

Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function $f : \{-1, 1\}^n \to \{-1, 1\}$ and $\bullet : \{-1, 1\}^2 \to \{-1, 1\}$ the two-party bounded-error quantum communication complexity of $(f \circ \bullet)$ is $O(Q(f) \log n)$, where $Q(f)$ is the bounded-error quantum query complexity of $f$. ... more >>>