Lifting Theorems for Equality.

We show a deterministic simulation (or lifting) theorem for composed problems f ◦Eqn where the9 inner function (the gadget) is Equality on n bits. When f is a total function on p bits, it is easy to10 show via a rank argument that the communication complexity of f ◦Eqn is Ω(deg(f)·n). However,11 there is a surprising counter-example of a partial function f on p bits, such that any completion f012 of f has deg(f0) = Ω(p), and yet f ◦Eqn has communication complexity O(n). Nonetheless, we are13 able to show that the communication complexity of f ◦Eqn is at least D(f)·n for a complexity14 measure D(f) which is closely related to the AND-query complexity of f and is lower-bounded by15 the logarithm of the leaf complexity of f. As a corollary, we also obtain lifting theorems for the16 set-disjointness gadget, and a lifting theorem in the context of parity decision-trees, for the NOR17 gadget.18 As an application, we prove a tight lower-bound for the deterministic communication complexity19 of the communication problem, where Alice and Bob are each given p-many n-bit strings, with the20 promise that either all of the strings are distinct, or all-but-one of the strings are distinct, and they21 wish to know which is the case. We show that the complexity of this problem is Θ(p·n).QC 20190412