We show a deterministic simulation (or lifting) theorem for composed problems f E Q 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 E Q n is ( de g ( f ) n ) . However, there is a surprising counter-example of a partial function f on p bits, such that any completion f of f has de g ( f ) = ( p ) , and yet f E Q n has communication complexity O ( n ) . Nonetheless, we are able to show that the communication complexity of f E Q n is at least D ( f ) n for a complexity measure D ( f ) which is closely related to the AN D -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 NO R 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 ( p n ) .