Data structure lower bound

Simulation Beats Richness: New Data-Structure Lower Bounds

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