Simulation theorem

We show a deterministic simulation (or lifting) theorem for composed problems $f\circ {\mathsf{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 {\mathsf{Eq}}_n$ is $\mathrm{\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^{\prime }$ of $f$ has $\mathrm{deg}(f^{\prime })=\mathrm{\Omega }(p)$, and yet $f\circ {\mathsf{Eq}}_n$ has communication complexity $O(n)$.

We develop a technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC'94) and Miltersen, Nisan, Safra and Wigderson (STOC'95). At the core of our technique is a novel simulation theorem. Alice gets a $p\times n$ matrix $x$ over ${\mathbb{F}}_2$ and Bob gets a vector $y\in {\mathbb{F}}_2^n$. Alice and Bob need to evaluate $f(x\cdot y)$ for a Boolean function $f$.