Lifting randomized query complexity to randomized communication complexity

Anurag Anshu, Naresh B. Goud, Rahul Jain +2

We show that for a relation $f\subseteq \{0,1{\}}^n\times \mathcal{O}$ and a function $g:\{0,1{\}}^m\times \{0,1{\}}^m\to \{0,1\}$ (with $m=O(\log n)$), $$\mathrm{R}_{1/3}(…