Lifting theorems for equality
Bruno Loff, Sagnik Mukhopadhyay · University of Birmingham Research Portal (University of Birmingham) · 2019
We show a deterministic simulation (or lifting) theorem for composed problems f ◦ Eqn 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 ◦ Eqn is Ω(deg(f) · n). However, there is a surprising counter-example of a partial function f on p bits, such that any completion f0 of f has deg(f0) = Ω(p), and yet f ◦ Eqn has communication complexity O(n). Nonetheless, we are able to show that the communication complexity of f ◦ Eqn is at least D(f) · 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 Θ(p · n).