Abstract
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 new simulation theorem: Alice gets a p by n matrix X over F2 and Bob gets a vector y in (F-2)^n. Alice and Bob need to evaluate f(X.y) for a Boolean function f:{0,1}^p → {0,1} . Our simulation theorems show that a deterministic/randomized communication protocol exists for this problem, with cost C·n for Alice and C for Bob, if and only if there exists a deterministic/randomized parity decision tree of cost about C for evaluating f.
We provide applications of this theorem to obtain new lower bounds for static data-structure problems like Vector-Matrix-Vector product and Orthogonal Vector counting. We also show there are problems for which the simulation theorem yields significantly better bounds than what the richness technique of Miltersen et al. provides.
Joint work with Michal Koucky, Bruno Loff and Sagnik Mukhopadhyay.