Data structure lower bound

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$.