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$ is $\Omega(deg(f) \cdot n)$. However, there is a surprising counter-example of a partial function $f$ on $p$ bits, such that any completion $f'$ of $f$ has $deg(f') = \Omega(p)$, and yet $f \circ EQ_n$ has communication complexity $O(n)$. Nonetheless, we are able to show that the communication complexity of $f \circ EQ_n$ is at least $D(f) \cdot n$ for a complexity measure $D(f)$ which is closely related to the $AND$-query complexity of $f$ and is lower-bounded by the logarithm of the leaf complexity of $f$. As a corollary, we also obtain lifting theorems for the set-disjointness gadget, and a lifting theorem in the context of parity decision-trees, for the $NOR$ gadget.

As an application, we prove a tight lower bound for the deterministic communication complexity of the communication problem, where Alice and Bob are each given $p$-many $n$-bit strings, with the promise that either all of the strings are distinct, or all-but-one of the strings are distinct, and they wish to know which is the case. We show that the complexity of this problem is $\Theta(p \cdot n)$.

Changed tea-break puzzle and simplified some proof.

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$ is $\Omega(deg(f) \cdot n)$. However, there is a surprising counter-example of a partial function $f$ on $p$ bits, such that any completion $f'$ of $f$ has $deg(f') = \Omega(p)$, and yet $f \circ EQ_n$ has communication complexity $O(n)$. Nonetheless, we are able to show that the communication complexity of $f \circ EQ_n$ is at least $D(f) \cdot n$ for a complexity measure $D(f)$ which is closely related to the $AND$-query complexity of $f$ and is lower-bounded by the logarithm of the leaf complexity of $f$. As a corollary, we also obtain lifting theorems for the set-disjointness gadget, and a lifting theorem in the context of parity decision-trees, for the $NOR$ gadget.

As an application, we prove the first tight lower-bound for the deterministic communication complexity of the natural Gap-Equality problem, where Alice and Bob are each given $p$-many $n$-bit strings, with the promise that either $\frac{3}{4}$ of them are equal or $\frac{3}{4}$ of them are different, and they wish to know which is the case. We show that the complexity of this problem is $\Theta(p \cdot n)$.

Fixed a few typographical errors.

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$ is $\Omega(deg(f) \cdot n)$. However, there is a surprising counter-example of a partial function $f$ on $p$ bits, such that any completion $f'$ of $f$ has $deg(f') = \Omega(p)$, and yet $f \circ EQ_n$ has communication complexity $O(n)$. Nonetheless, we are able to show that the communication complexity of $f \circ EQ_n$ is at least $D(f) \cdot n$ for a complexity measure $D(f)$ which is closely related to the $AND$-query complexity of $f$ and is lower-bounded by the logarithm of the leaf complexity of $f$. As a corollary, we also obtain lifting theorems for the set-disjointness gadget, and a lifting theorem in the context of parity decision-trees, for the $NOR$ gadget.

As an application, we prove the first tight lower-bound for the deterministic communication complexity of the natural Gap-Equality problem, where Alice and Bob are each given $p$-many $n$-bit strings, with the promise that either $\frac{3}{4}$ of them are equal or $\frac{3}{4}$ of them are different, and they wish to know which is the case. We show that the complexity of this problem is $\Theta(p \cdot n)$.